ECCC-Report TR06-064https://eccc.weizmann.ac.il/report/2006/064Comments and Revisions published for TR06-064en-usMon, 08 May 2006 18:36:45 +0300
Paper TR06-064
| Note on MAX 2SAT |
Moses Charikar,
Konstantin Makarychev,
Yury Makarychev
https://eccc.weizmann.ac.il/report/2006/064 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.
Mon, 08 May 2006 18:36:45 +0300https://eccc.weizmann.ac.il/report/2006/064