Takao Asano
David P. Williamson
Index Terms
- Improved approximation algorithms for MAX SAT
Recommendations
Improved Approximation Algorithms for MAX SAT
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 ...
Improved approximation algorithms for MAX NAE-SAT and MAX SAT
WAOA'05: Proceedings of the Third international conference on Approximation and Online AlgorithmsMAX SAT and MAX NAE-SAT are central problems in theoretical computer science. We present an approximation algorithm for MAX NAE-SAT with a conjectured performance guarantee of 0.8279. This improves a previously conjectured performance guarantee of ...
Approximation Algorithms for MAX SAT: Yannakakis vs. Goemans-Williamson
ISTCS '97: Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97)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 ...
Comments