An Improvement of Yannakakis'Algorithm for MAX SAT
Takao Asano · Institutional Repositories DataBase (IRDB) · 2004
MAX SAT(maximum satisfiability problem) is stated as fllows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we consider approximation algorithms for MAX SAT proposed by Yannakakis and Goemans-Williamson and present an approximation algorithm which is an improvement of Yannakakis’ alforithm. Althoufh Yannakakis’ original algoritm has no better perfoemance guarantee than Goemans-Williamson, our improved algorithm has a better performance guarantee and leads to a 0.770-approximation algorithm.