Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
2018-06-30T08:28:36Z (GMT) by
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.