Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?

Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell

Research output: Contribution to journalArticle

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 α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. 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 hardness factor which asymptotically (for large q) matches the approximation factor achieved by Frieze and Jerrum [Improved approximation algorithms for MAX k-CUT and MAX BISECTION, in Integer Programming and Combinatorial Optimization, Springer-Verlag, Berlin, pp. 1-13], namely 1 - 1/q + 2(In q)/q2. For MAX-2LIN(q) we show hardness of distinguishing between instances which are (1 - ε)-satisfiable and those which are not even, roughly, (q-ε/2)-satisfiable. These parameters almost match those achieved by the recent algorithm of Charikar, Makarychev, and Makarychev [Proceedings of the 38th .Annital ACM Symposium on Theory of Computing, 2006, pp. 205-214]. The hardness result holds even for instances in which all equations are of the form Xi -Xj = c. At a more qualitative level, this result also implies that 1 - ε vs. ε hardness for MAX-2LIN(q) is equivalent to the Unique Games Conjecture.

Original languageEnglish (US)
Pages (from-to)319-357
Number of pages39
JournalSIAM Journal on Computing
Volume37
Issue number1
DOIs
StatePublished - 2007

Keywords

  • Constraint satisfaction
  • Hardness of approximation
  • MAX-CUT
  • Unique games

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?'. Together they form a unique fingerprint.

  • Cite this