Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR06-088 | 9th July 2006 00:00

#### Balanced Max 2-Sat might not be the hardest

TR06-088
Authors: Per Austrin
Publication: 26th July 2006 21:59
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.