Abstract:

In this work, we study approximation algorithms based on semidefinite programming (SDP) for which the performance guarantee involves a non-local analysis, and in some instances a non-local SDP relaxation.

We examine two such approaches. The first of these is inspired by recent work of Arora, Rao and Vazirani on Sparsest Cut. Using a geometric intuition similar to theirs, we give an algorithm for coloring 3-colorable graphs which is nearly identical to that of Blum and Karger, and finds a legal coloring which uses roughly O (n0.2130 ) as opposed to the original O (n0.2143 ) guarantee in that paper.

The second approach makes use of SDP hierarchies, on which prior work has yielded mostly negative results. Using this method, we give an algorithm for coloring 3-colorable graphs which finds a legal O ( n0.2072 )-coloring.

As an additional application of this approach, in 3-uniform hypergraphs containing an independent set of size ?n (for any constant ? > 0), we describe an algorithm which finds an independent set of size [Special characters omitted.] using the ?(1/?2 )-level of an SDP hierarchy. We also present integrality gaps for this hierarchy which imply improved performance guarantees as one uses progressively higher-level SDP relaxations.