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

By Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel. 45th Annual IEEE Symposium on Foundations of Computer Science, 2004

885 citations recorded by the source corpus.

In this paper, we give evidence suggesting that MAX-CUT is NP-hard to approximate to within a factor of /spl alpha//sub cw/+ /spl epsi/, for all /spl epsi/ > 0, where /spl alpha//sub cw/ denotes the approximation ratio achieved by the Goemans-Williamson algorithm (1995). /spl alpha//sub cw/ /spl ap/ .878567. This result is conditional, relying on two conjectures: a) the unique games conjecture of Khot; and, b) a very believable conjecture we call the majority is stablest conjecture. These results indicate that the geometric nature of the Goemans-Williamson algorithm might be intrinsic to the MAX-CUT problem. The same two conjectures also imply that it is NP-hard to (/spl beta/ + /spl epsi/)-approximate MAX-2SAT, where /spl beta/ /spl ap/ .943943 is the minimum of (2 + (2//spl pi/) /spl theta/)/(3 - cos(/spl theta/)) on (/spl pi//2, /spl pi/). Motivated by our proof techniques, we show that if the MAX-2CSP and MAX-2SAT problems are slightly restricted - in a way that seems to retain all their hardness -then they have (/spl alpha//sub GW/-/spl epsi/)- and (/spl beta/ - /spl epsi/)-approximation algorithms, respectively. Though we are unable to prove the majority is stablest conjecture, we give some partial results and indicate possible directions of attack. Our partial results are enough to imply that MAX-CUT is hard to (3/4 + 1/(2/spl pi/) + /spl epsi/)-approximate (/spl ap/ .909155), assuming only the unique games conjecture. We also discuss MAX-2CSP problems over non-Boolean domains and state some related results and conjectures. We show, for example, that the unique games conjecture implies that it is hard to approximate MAX-2LIN(q) to within any constant factor.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/0b680813894f41339855e968fb4a638b20a82da8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into 1 (Extended Abstract) (2005, background): “This nicely complements the result of Khot et al. [ 20 ], where it is shown that, assuming the Unique Games Conjecture (UGC), it isNP-hard to approximate MAXIMUM CUT within a factor better than αGW + δ.”
FENNEL: streaming graph partitioning for massive scale graphs (2014, background): “…is p ( θ ) where As we see from Lemma 5 in [19], for this θ , the asymptotic expression of N k (cos ( θ )), which is equal to ours p ( θ ) but with their rounding scheme, matches ours: This suggests that our approximation factor may be the best optimal assuming the unique games conjecture [36, 35].”
Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry (2011, background): “2The original conjecture is stated in terms of a more general problem, but it is shown in [29] that the conjecture is equivalent to the statement here in terms of linear unique games.”
The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/ (2005, background): “We say that a space (X1, d1) embeds with distortion at most into another space (X2, d2) if there exists a map φ : X1 → X2 such that for all x, y ∈ X1 d1(x, y) ≤ d2(φ(x), φ(y)) ≤ · d1(x, y).”
Online Submodular Maximization with Preemption (2015, background): “878 [40, 49], and this hardness result holds also for Max-DiCut since the last generalizes Max-Cut.”
Hardness results for agnostically learning low-degree polynomial threshold functions (2010, methodology): “We use the statement from [18] which is equivalent to the original Unique Games Conjecture.”
Decidability of Non-interactive Simulation of Joint Distributions (2016, methodology): “ay take w = O 1+ρ α·(1−ρ)3·ζ2 , where α is the minimum non-zero probability in the distribution (X,Y ). In order to prove Lemma 2.22, we need the following statement that appears as Theorem 16 in [KKMO07] and as Corollary 16.3 in [BR86]. Theorem 2.23. Let Z 1,...,Zw be independent random variables”
The Design of Approximation Algorithms (2011, background): “15 is due to Khot, Kindler, Mossel, and O’Donnell [193] together with a result of Mossel, O’Donnell, and Oleszkiewicz [227].”
Maximizing Non-Monotone Submodular Functions (2011, background): “An alternative definition of submodularity is the property of decreasing marginal values: For any A ⊆ B ⊆ X and x ∈ X \ B, f (B ∪ {x}) − f (B) ≤ f (A ∪ {x}) − f (A).”