Approximation Algorithms for MAX SAT : Semidefinite Programming and Network Flows Approach
Takao Asano, Kuniaki Hori, Takao Ono, Tomio Hirata · Institutional Repositories DataBase (IRDB) · 1997
MAX SAT (the maximum satisfiability problem) is stated as follows: 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 present an approximation algorithm for MAX SAT which is a refinement of Yannakakis's algorithm.This algorithm leads to a better approximation algorithm with performance guarantee 0.767 if it is combined with the previous algorithms for MAX SAT.