Abstract
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
SIAM Journal on Computing, Vol.37(1), pp.319-357
45th Annual IEEE Symposium on Foundations of Computer Science (Rome, ITALY, 17/Oct/2004 - 19/Oct/2004)
2007
Abstract
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of alpha(GW) + is an element of for all is an element of > 0; here alpha(GW) approximate to .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. Our reduction relies on a theorem we call Majority Is Stablest. This was introduced as a conjecture in the original version of this paper, and was subsequently confirmed in [E. Mossel, R. O'Donnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 21 - 30]. A stronger version of this conjecture called Plurality Is Stablest is still open, although [ E. Mossel, R. O'Donnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 21 - 30] contains a proof of an asymptotic version of it. Our techniques extend to several other two-variable constraint satisfaction problems. In particular, subject to the Unique Games Conjecture, we show tight or nearly tight hardness results for MAX-2SAT, MAX-q-CUT, and MAX-2LIN(q). For MAX-2SAT we show approximation hardness up to a factor of roughly .943. This nearly matches the .940 approximation algorithm of Lewin, Livnat, and Zwick in [ Proceedings of the 9th Annual Conference on Integer Programming and Combinatorial Optimization, Springer-Verlag, Berlin, 2002, pp. 67 82]. Furthermore, we show that our .943...factor is actually tight for a slightly restricted version of MAX-2SAT. For MAX-q-CUT we show a hardn
Details
- Title
- Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
- Creators
- Subhash Khot (null)Guy Kindler (null)Elchanan Mossel (null) - 972WIS_INST___83Ryan O'Donnell (null)
- Resource Type
- Abstract
- Publication Details
- SIAM Journal on Computing, Vol.37(1), pp.319-357; 2007
- Number of pages
- 39
- Language
- English
- DOI
- https://doi.org/10.1137/S0097539705447372
- Conference
- 45th Annual IEEE Symposium on Foundations of Computer Science (Rome, ITALY, 17/Oct/2004 - 19/Oct/2004)
- Record Identifier
- 993262566703596
Metrics
9 Record Views