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-088 | 9th July 2006 00:00

Balanced Max 2-Sat might not be the hardest

RSS-Feed




TR06-088
Authors: Per Austrin
Publication: 26th July 2006 21:59
Downloads: 1292
Keywords: 


Abstract:

We 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%.



ISSN 1433-8092 | Imprint