Tight approximability of MAX 2-SAT and relatives, under UGC

Joshua Brakensiek, Neng Huang, Uri Zwick

Austrin showed that the approximation ratio $\beta \approx 0.94016567$ obtained by the MAX 2-SAT approximation algorithm of Lewin, Livnat and Zwick (LLZ) is optimal modulo the Unique Ga…