NDLI: Optimal Inapproximability Results for MAXCUT and Other 2Variable CSPs?

Please wait, while we are loading the content...

Optimal Inapproximability Results for MAXCUT and Other 2Variable CSPs?

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Khot, Subhash Kindler, Guy Mossel, Elchanan ODonnell, Ryan
Copyright Year	2007
Abstract	In this paper we show a reduction from the Unique Games problem to the problem of approximating MAXCUT to within a factor of $\alpha_{\text{\tiny{GW}}} + \epsilon$ for all $\epsilon > 0$; here $\alpha_{\text{\tiny{GW}}} \approx .878567$ denotes the approximation ratio achieved by the algorithm of Goemans and Williamson in J. Assoc. Comput. Mach., 42 1995, pp. 11151145. This implies that if the Unique Games Conjecture of Khot in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 767775 holds, then the GoemansWilliamson approximation algorithm is optimal. Our result indicates that the geometric nature of the GoemansWilliamson algorithm might be intrinsic to the MAXCUT 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. ODonnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 2130. A stronger version of this conjecture called Plurality Is Stablest is still open, although E. Mossel, R. ODonnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 2130 contains a proof of an asymptotic version of it. Our techniques extend to several other twovariable constraint satisfaction problems. In particular, subject to the Unique Games Conjecture, we show tight or nearly tight hardness results for MAX2SAT, MAXqCUT, and MAX2LINq. For MAX2SAT 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, SpringerVerlag, Berlin, 2002, pp. 6782. Furthermore, we show that our .943... factor is actually tight for a slightly restricted version of MAX2SAT. For MAXqCUT we show a hardness factor which asymptotically for large q matches the approximation factor achieved by Frieze and Jerrum Improved approximation algorithms for MAX kCUT and MAX BISECTION, in Integer Programming and Combinatorial Optimization, SpringerVerlag, Berlin, pp. 113, namely $1 - 1/q + 2({\rm ln}\,q)/q^2$. For MAX2LINq we show hardness of distinguishing between instances which are $(1-\epsilon)$satisfiable and those which are not even, roughly, $(q^{-\epsilon/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. 205214. The hardness result holds even for instances in which all equations are of the form $x_i - x_j = c$. At a more qualitative level, this result also implies that $1-\epsilon$ vs. hardness for MAX2LINq is equivalent to the Unique Games Conjecture.
Starting Page	319
Ending Page	357
Page Count	39
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539705447372
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1 (Special Section on Foundations of Computer Science)
Volume Number	37
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2007-05-14
Access Restriction	Subscribed
Subject Keyword	Computational difficulty of problems constraint satisfaction Unique Games hardness of approximation MAXCUT
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Towards Sharp Inapproximability for Any 2-CSP

Optimal inapproximability results for max-cut and other 2variable CSPs (2004)

Optimal inapproximability results for max-cut and other 2-variable csps (2007).

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

Optimal Inapproximability Results for MAX-CUT and other 2-variable CSPs? (2005)

Optimal inapproximability results for MAX-CUT and other 2-variable CSPs (2005)

Conditional Hardness for Approximate Coloring

The Approximability of Constraint Satisfaction Problems

Nearly Optimal NP-Hardness of Unique Coverage

Optimal Inapproximability Results for MAXCUT and Other 2Variable CSPs?

Similar Documents

Towards Sharp Inapproximability for Any 2-CSP

Optimal inapproximability results for max-cut and other 2variable CSPs (2004)

Optimal inapproximability results for max-cut and other 2-variable csps (2007).

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

Optimal Inapproximability Results for MAX-CUT and other 2-variable CSPs? (2005)

Optimal inapproximability results for MAX-CUT and other 2-variable CSPs (2005)

Conditional Hardness for Approximate Coloring

The Approximability of Constraint Satisfaction Problems

Nearly Optimal NP-Hardness of Unique Coverage

Optimal Inapproximability Results for MAXCUT and Other 2Variable CSPs?