ECCC-Report TR06-088https://eccc.weizmann.ac.il/report/2006/088Comments and Revisions published for TR06-088en-usWed, 26 Jul 2006 21:59:31 +0300
Paper TR06-088
| Balanced Max 2-Sat might not be the hardest |
Per Austrin
https://eccc.weizmann.ac.il/report/2006/088We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate Max 2-Sat within $\alpha_{LLZ}^{-}+\epsilon$, where $0.9401 < \alpha_{LLZ}^{-} < 0.9402$ is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick.
This result is surprising considering the fact that balanced instances of Max 2-Sat, i.e. instances where each variable occurs positively and negatively equally often, can be approximated within 0.9439. In particular, instances in which roughly 70% of the literals are unnegated variables and 30% are negated appear less amenable to approximation than instances where the ratio is 50%-50%.
Wed, 26 Jul 2006 21:59:31 +0300https://eccc.weizmann.ac.il/report/2006/088