Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
Subhash Khot
Guy Kindler
Elchanan Mossel
Ryan O'Donnell
10.1184/R1/6608114.v1
https://kilthub.cmu.edu/articles/journal_contribution/Optimal_Inapproximability_Results_for_MAX-CUT_and_Other_2-Variable_CSPs_/6608114
In this paper we show a reduction from the Unique Games problem to the problem
of approximating MAX-CUT to within a factor of αGW+ε for all ε > 0; here αGW ≈ .878567 denotes
the approximation ratio achieved by the algorithm of Goemans and Williamson in [J. Assoc. Comput.
Mach., 42 (1995), pp. 1115–1145]. This implies that if the Unique Games Conjecture of Khot
in [Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775]
holds, then the Goemans–Williamson approximation algorithm is optimal. Our result indicates that
the geometric nature of the Goemans–Williamson algorithm might be intrinsic to the MAX-CUT
problem.
1982-01-01 00:00:00
computer sciences