About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Algorithms
Paper
Improved approximation algorithms for MAX SAT
Abstract
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 consider approximation algorithms for MAX SAT proposed by Goemans and Williamson and present a sharpened analysis of their performance guarantees. We also show that these algorithms, combined with recent approximation algorithms for MAX 2SAT, MAX 3SAT, and MAX SAT due to Feige and Goemans, Karloff and Zwick, and Zwick, respectively, lead to an improved approximation algorithm for MAX SAT. By using the MAX 2SAT and 3SAT algorithms, we obtain a performance guarantee of 0.7846, and by using Zwick's algorithm, we obtain a performance guarantee of 0.8331, which improves upon the performance guarantee of 0.7977 based on Zwick's conjecture. The best previous result for MAX SAT without assuming Zwick's conjecture is a 0.770-approximation algorithm of Asano. Our best algorithm requires a new family of 3/4-approximation algorithms that generalize a previous algorithm of Goemans and Williamson.