I detta papper presenterar vi förbättrade exakta och parameteriserade algoritmer för maximal tillfredsställelse problem. I synnerhet, vi ger en algoritm som beräknar en sanning uppdrag för en boolesk formel F uppfyller det maximala antalet klausuler i tid O(1.3247 m  på F), där m är antalet klausuler i F, och  på F är summan av antalet ordagranna som visas i varje klausul i F. Dessutom, med tanke på en parameter k, ger vi en O(1.3695 k +  på F) parameteriserad algoritm som avgör om en sanning uppdrag för F uppfyller minst k klausuler finns. Båda algoritmerna förbättrar de tidigare bästa algoritmerna av Bansal och Raman för problemet.
För närvarande är den bästa algoritmen som ges i REF och löser detta problem i O(1.37 k +  på F), där  och F är storleken på den givna formeln.
Improved Exact Algorithms for MAX-SAT
{'venue': 'LATIN', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}