The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/

By Subhash Khot, Nisheeth K. Vishnoi. IEEE Annual Symposium on Foundations of Computer Science, 2005

322 citations recorded by the source corpus.

In this paper, we disprove the following conjecture due to Goemans (1997) and Linial (2002): "Every negative type metric embeds into with constant distortion." We show that for every /spl delta/ > 0, and for large enough n, there is an n-point negative type metric which requires distortion at-least (log log n) /sup 1/6-/spl delta// to embed into l/sub 1/. Surprisingly, our construction is inspired by the Unique Games Conjecture (UGC) of Khot (2002), establishing a previously unsuspected connection between PCPs and the theory of metric embeddings. We first prove that the UGC implies super-constant hardness results for (non-uniform) sparsest cut and minimum uncut problems. It is already known that the UGC also implies an optimal hardness result for maximum cut (2004). Though these hardness results depend on the UGC, the integrality gap instances rely "only" on the PCP reductions for the respective problems. Towards this, we first construct an integrality gap instance for a natural SDP relaxation of unique games. Then, we "simulate" the PCP reduction and "translate"the integrality gap instance of unique games to integrality gap instances for the respective cut problems! This enables us to prove a (log log n) /sup 1/6-/spl delta// integrality gap for (nonuniform) sparsest cut and minimum uncut, and an optimal integrality gap for maximum cut. All our SDP solutions satisfy the so-called "triangle inequality" constraints. This also shows, for the first time, that the triangle inequality constraints do not add any power to the Goemans-Williamson's SDP relaxation of maximum cut. The integrality gap for sparsest cut immediately implies a lower bound for embedding negative type metrics into l/sub i/. It also disproves the non-uniform version of Arora, Rao and Vazirani's Conjecture (2004), asserting that the integrality gap of the sparsest cut SDP, with the triangle inequality constraints, is bounded from above by a constant.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/4a403a3f58051508c383b2d234dd662a824caa7d

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? (2004, background): “But in fact, it is easy to observe that the “non-bipartite” version of the Unique Games Conjecture is equivalent to the usual Unique Games Conjecture [ 38 ] (up to a factor of 2 in the soundness).”
Vertex cover might be hard to approximate to within 2-/spl epsiv/ (2003, background): “[6] and independently, Khot and Vishnoi [24] prove super-constant hardness results for the Sparsest Cut and Multi-Cut problems; Dinur, Mossel, and Regev [9] prove that a variant of the unique games conjecture implies that it is NP-hard to color 3-colorable graphs with any constant number of colors.”
Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry (2011, background): “2 gives the following inapproximability result proved by Khot and Vishnoi [34].”
Optimal algorithms and inapproximability results for every CSP? (2008, methodology): “Unconditional Results: Using the Unique games integrality gap of Khot-Vishnoi [16], we convert the UG hardness results to integrality gaps for SDP(II) and SDP(III).”
Warm-starting quantum optimization (2020, background): “The well-known Unique Games Conjecture [53–55] suggests that GW randomized rounding has the best possible polynomial-time performance on MAXCUT.”
Towards Sharp Inapproximability For Any 2-CSP (2007, unknown): “Examples of such results include 2 − hardness for VERTEX COVER [24], superconstant hardness for SPARSESTCUT [10, 25] and MULTICUT [10], hardness of approximating M AX INDEPENDENTSET within d/poly(log d) in degreed graphs [31], and approximation resistance 2 for random predicates [19].”
Improved approximation algorithms for minimum-weight vertex separators (2005, background): “Very recent work of Khot and Vishnoi [28] shows that in the non-uniform demand case, the gap must tend to in.nity with the size of the instance.”