Yi Wu

Title: An Optimal SDP Approximation Algorithm for Max-Cut

Abstract:

Abstract:
Let G be an undirected graph for which the standard Max-Cut SDP
relaxation achieves at least a c fraction of the total edge weight,
1/2  < c< 1. If the actual optimal cut for G is at most an s fraction
of the total edge weight, we say that (c, s) is an SDP gap. We define
the SDP gap curve GapSDP : [ 1/2 , 1] ->[ 1/2 , 1]  by  GapSDP (c) =
inf {s : (c, s) is an SDP gap}.
We complete a long line of work by determining the entire SDP gap
curve; we show GapSDP (c) = S (c) for a certain explicit (but
complicated to state) function S . In particular, our lower bound
GapSDP(c) <=S (c) is proved via a polynomial-time 'RPR2 ' algorithm.
Thus we have given an efficient, optimal
SDP-rounding algorithm for Max-Cut. The fact that it is RPR2 confirms
a conjecture of Feige and Langberg.
We also describe and analyze the tight connection between SDP gaps and
Long Code tests. Using this connection, we give optimal Long Code
tests for
Max-Cut. We reach the following conclusion:
• The Max-Cut SDP gap curve subject to triangle inequalities is also
given by S (c).
• No RPR2 algorithm can be guaranteed to find cuts of value larger
than S (c) in graphs where the optimal cut is c. (Contrast this with
the fact that in the graphs exhibiting the c vs. S (c) SDP gap, our
RPR2 algorithm actually finds the optimal cut.)
• Further, no polynomial-time algorithm of any kind can have such a
guarantee, assuming P  != NP and the Unique Games Conjecture.