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