Time: 12:00pm 2008-02-19
Place: NSH 1507
Speaker: Yi Wu
Title: An Optimal SDP Approximation Algorithm for Max-Cut
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 \leq c \leq 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] \rightarrow [1/2, 1]$ by $GapSDP(c) = \text{inf} {s : (c, s) \text{ 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) \geq S(c)$ is proved via a polynomial-time ‘$\text{RPR}^2$’ algorithm. Thus we have given an efficient, optimal SDP-rounding algorithm for Max-Cut. The fact that it is $\text{RPR}^2$ 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 conclusions:
- The Max-Cut SDP gap curve subject to triangle inequalities is also given by $S(c)$.
- No $\text{RPR}^2$ 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 $\text{RPR}^2$ 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.
