Approximation algorithms for the maximum satisfiability problem
Takao Asano, Takao Ono, Tomio Hirata · Nordic journal of computing · 1996
The maximum satisfiability problem (MAX SAT) is the following: 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 approximation algorithms for MAX SAT, including a 0.76544-approximation algorithm. The previous best approximation algorithm for MAX SAT was proposed by Goemans-Williamson and has a performance guarantee of 0.7584. Our algorithms are based on semidefinite programming and the 0.75-approximation algorithms of Yannakakis and Goemans-Williamson.