Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-064 | 1st May 2006 00:00

Note on MAX 2SAT

RSS-Feed

Abstract:

In this note we present an approximation algorithm for MAX 2SAT that given a (1 - epsilon) satisfiable instance finds an assignment of variables satisfying a 1 - O(sqrt{epsilon}) fraction of all constraints. This result is optimal assuming the Unique Games Conjecture.

The best previously known result, due to Zwick, was 1 - O(epsilon^{1/3}). We believe that the analysis of our algorithm is much simpler than the analysis of Zwick's algorithm.



ISSN 1433-8092 | Imprint