DocumentCode
2261938
Title
Approximation algorithms for MAX SAT: Yannakakis vs. Goemans-Williamson
Author
Asano, Takao
Author_Institution
Dept. of Inf. & Syst. Eng., Chuo Univ., Tokyo, Japan
fYear
1997
fDate
17-19 Jun 1997
Firstpage
24
Lastpage
37
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 Yannnkakis and Goemans-Williamson and present an approximation algorithm which is an improvement of Yannakakis´ algorithm. Although Yannakakis´ original algorithm has no better performance guarantee than Goemans-Williamson, our improved algorithm has a better performance guarantee and leads to a 0.770 approximation algorithm
Keywords
approximation theory; computability; computational complexity; MAX SAT; approximation algorithms; clauses; maximum satisfiability problem; truth assignment; weights; Approximation algorithms; Educational programs; Polynomials; Programming profession; Systems engineering and theory;
fLanguage
English
Publisher
ieee
Conference_Titel
Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on
Conference_Location
Ramat-Gan
Print_ISBN
0-8186-8037-7
Type
conf
DOI
10.1109/ISTCS.1997.595154
Filename
595154
Link To Document