Result: OPTIMAL INAPPROXIMABILITY RESULTS FOR MAX-CUT AND OTHER 2-VARIABLE CSPs?
Faculty of Mathematics and Computer Science, Weizmann Institute of Science, 44453 Kfar Saba, Israel
Department of Statistics, University of California at Berkeley, Berkeley, CA 94720, United States
Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, United States
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Mathematics
Further Information
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(ln q)/q2. For MAX-2LIN(q) we show hardness of distinguishing between instances which are (1 - e)-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 Annual 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. e hardness for MAX-2LIN(q) is equivalent to the Unique Games Conjecture.