摘要: MAX SAT (the maximum satisfiability problem) is stated as follows: given a set of clauses with weights, find truth assignment that maximizes the sum weights satisfied clauses. In this paper, we consider approximation algorithms for proposed by Goemans and Williamson present sharpened analysis their performance guarantees. We also show these algorithms, combined recent 2SAT, 3SAT, due to Feige Goemans, Karloff Zwick, respectively, lead an improved algorithm SAT. By using 2SAT 3SAT obtain guarantee 0.7846, Zwick's algorithm, 0.8331, which improves upon 0.7977 based on conjecture. The best previous result without assuming conjecture 0.770-approximation Asano. Our requires new family 34-approximation generalize Williamson.
core.ac.uk
elsevier.com
sci-hub.se 参考文章(18)
Takao Ono, Tomio Hirata, Takao Asano, Approximation algorithms for the maximum satisfiability problem Nordic Journal of Computing. ,vol. 3, pp. 388- 404 ,(1996)
Michel X. Goemans, David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming Journal of the ACM. ,vol. 42, pp. 1115- 1145 ,(1995) , 10.1145/227683.227684
M. Yannakakis, On the approximation of maximum satisfiability symposium on discrete algorithms. ,vol. 17, pp. 1- 9 ,(1992) , 10.1006/JAGM.1994.1045
Michel X. Goemans, David P. Williamson, New ${\bf \frac{3}{4}}$-Approximation Algorithms for the Maximum Satisfiability Problem SIAM Journal on Discrete Mathematics. ,vol. 7, pp. 656- 666 ,(1994) , 10.1137/S0895480192243516
K. J. Lieberherr, E. Specker, Complexity of Partial Satisfaction Journal of the ACM. ,vol. 28, pp. 411- 421 ,(1981) , 10.1145/322248.322260
Uri Zwick, Outward rotations Proceedings of the thirty-first annual ACM symposium on Theory of computing - STOC '99. pp. 679- 687 ,(1999) , 10.1145/301250.301431
Eran Halperin, Uri Zwick, Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs Journal of Algorithms. ,vol. 40, pp. 184- 211 ,(2001) , 10.1006/JAGM.2001.1162
David S. Johnson, Approximation algorithms for combinatorial problems Journal of Computer and System Sciences. ,vol. 9, pp. 256- 278 ,(1974) , 10.1016/S0022-0000(74)80044-9
Michel X. Goemans, David P. Williamson, .879-approximation algorithms for MAX CUT and MAX 2SAT Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94. pp. 422- 431 ,(1994) , 10.1145/195058.195216
Johan Håstad, Some optimal inapproximability results symposium on the theory of computing. pp. 1- 10 ,(1997) , 10.1145/258533.258536