Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MAX 2-SAT:
Reports tagged with Max 2-Sat:
TR06-088 | 9th July 2006
Per Austrin

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

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. ... more >>>

ISSN 1433-8092 | Imprint