AbstractThe 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.
Categories and Subject Descriptors: G.1.6 [Numerical Analysis]: Optimization; G.2.1 [Discrete Mathematics]: Combinatorics; G.3 [Probability and Statistics]; I.1.2 [Algebraic Manipulation]: Algorithms
Additional Key Words and Phrases: approximation algorithms, maximum satisfiability, network flows, randomized algorithms, semidefinite programming
Selected references
- Michel X. Goemans and David P. Williamson. .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 422-431, Montréal, Québec, Canada, 23-25 May 1994.
- Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115-1145, November 1995.
- David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256-278, December 1974.
- Sanjeev Mahajan and H. Ramesh. Derandomizing semidefinite programming based approximation algorithms. In 36th Annual Symposium on Foundations of Computer Science, pages 162-169, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.
- Mihalis Yannakakis. On the approximation of maximum satisfiability. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1-9, Orlando, Florida, 27-29 January 1992.
- Mihalis Yannakakis. On the approximation of maximum satisfiability. Journal of Algorithms, 17(3):475-502, November 1994.