Tight approximability of MAX 2-SAT and relatives, under UGC
Joshua Brakensiek, Neng Huang, Uri Zwick · Society for Industrial and Applied Mathematics eBooks · 2024
Austrin showed that the approximation ratio β ≈ 0.94016567 obtained by the MAX 2-SAT approximation algorithm of Lewin, Livnat and Zwick (LLZ) is optimal modulo the Unique Games Conjecture (UGC) and modulo a Simplicity Conjecture that states that the worst performance of the algorithm is obtained on so called simple configurations. We prove Austrin's conjecture, thereby showing the optimality of the LLZ approximation algorithm, relying only on the Unique Games Conjecture. Our proof uses a combination of analytic and computational tools.