### DIMACS Theoretical Computer Science Seminar

Title: Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT

Speaker: **Adi Avidor**, Tel-Aviv University

Date: September 6, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Goemans and Williamson obtained an approximation algorithm for the
MAX CUT problem with a performance ratio of $\alpha_{GW}~
0.87856$. Their algorithm starts by solving a standard SDP
relaxation of MAX CUT and then rounds the optimal solution
obtained using a random hyperplane. In some cases, the optimal
solution of the SDP relaxation happens to lie in a low dimensional
space. Can an improved performance ratio be obtained for such
instances? We show that the answer is yes in dimensions two and
three and conjecture that this is also the case in any higher
fixed dimension. In two dimensions an optimal $32/(25+5\sqrt{5})$
approximation algorithm was already obtained by Goemans. (Note that
$32/(25+5\sqrt{5}) ~ 0.88456$.)
We obtain an alternative derivation of this result using Gegenbauer
polynomials. Our main result is an improved rounding procedure for
SDP solutions that lie in $R^3$ with a performance ratio of about
$0.8818$ . The rounding procedure uses an interesting yin-yan coloring
of the three dimensional sphere. The improved performance ratio
obtained resolves, in the negative, an open problem posed by Feige and
Schechtman [STOC'01]. They asked whether there are MAX CUT
instances with integrality ratios arbitrarily close to
$\alpha_{GW}~0.87856$ that have optimal embedding, i.e.,
optimal solutions of their SDP relaxations, that lie in $R^3$.

Joint work with Uri Zwick