Volume 5 (2009) Article 4 pp. 83-117

SDP Gaps and UGC-hardness for Max-Cut-Gain

by Subhash Khot and Ryan O'Donnell

Received: July 14, 2008
Published: May 29, 2009

Abstract: [Plain Text Version]

Given a graph with maximum cut of (fractional) size c, the semidefinite programming (SDP)-based algorithm of Goemans and Williamson is guaranteed to find a cut of size at least .878⋅ c. However this guarantee becomes trivial when c is near ½, since making random cuts guarantees a cut of size ½ (i.e., half of all edges). A few years ago, Charikar and Wirth (analyzing an algorithm of Feige and Langberg) showed that given a graph with maximum cut ½ + ε, one can find a cut of size ½ + Ω(ε / log (1 /ε)). The main contribution of our paper is twofold:

1. We give a natural and explicit ½ + ε   vs.  ½ + O(ε / log (1/ε)) integrality gap for the Max-Cut SDP based on Euclidean space with the Gaussian probability distribution. This shows that the SDP-rounding algorithm of Charikar-Wirth is essentially best possible.
2. We show how this SDP gap can be translated into a Long Code test with the same parameters. This implies that beating the Charikar-Wirth guarantee with any efficient algorithm is NP-hard, assuming the Unique Games Conjecture (UGC). This result essentially settles the asymptotic approximability of Max-Cut, assuming UGC.

Building on the first contribution, we show how “randomness reduction” on related SDP gaps for the Quadratic-Programming problem lets us make the Ω(log(1 / ε)) gap as large as Ω(log n) for n-vertex graphs. In addition to optimally answering an open question of Alon, Makarychev, Makarychev, and Naor, this technique may prove useful for other SDP gap problems.

Finally, illustrating the generality of our second contribution, we also show how to translate the Davie--Reeds SDP gap for the Grothendieck Inequality into a UGC-hardness result for computing the || ⋅ ||_{∞ ↦ 1} norm of a matrix.

© 2009 Subhash Khot and Ryan O'Donnell
Licensed under a Creative Commons Attribution License