Abstract:
Linear Programming (LP) and Semidefinite Programming (SDP) have been
used extensively to obtain approximation algorithms for combinatorial
optimization problems. One possible avenue of improvement for such
algorithms is the use of "lift-and-project" techniques, which, given
an Integer Program (IP) over $n$ 0-1 variables, define a hierarchy of
LP or SDP relaxations which converge to the convex hull of the
original IP solutions. Since the LP and SDP relaxations arising from
the $k$th level of such hierarchies can be solved in time $n^{O(k)}$,
one would hope to obtain improved approximations after a constant
number of iterations.
Unfortunately, for several problems (most prominently Vertex Cover),
it has been shown that for various LP and SDP hierarchies, the quality
of approximation (the integrality gap) does not improve substantially
even after many rounds of lift-and-project.
Here we consider SDP relaxations arising from the third level of the
Lasserre hierarchy, and show that they yield improved approximations
for two combinatorial problems.
The first problem is Maximum Independent Set in 3-uniform
hypergraphs. The previous best approximation for this problem was
given by Krivelevich, Nathaniel and Sudakov, who gave an algorithm
finding an independent set of size $\tilde{\Omega}(n^{6\gamma-3})$ for
3-uniform hypergraphs with an independent set of size $\gamma n$ (but
no guarantee when $\gamma \leq 1/2$). We show that for some fixed
constant $\epsilon > 0$, given a hypergraph containing an independent
set of size $(1/2-\epsilon)n$, we can find an independent set of size
$\Omega(n^{\epsilon})$.
The second problem we consider is that of legally coloring 3-colorable
graphs using a minimum number of colors. We give an algorithm which
finds an $O(n^{0.2072})$-coloring given a $3$-colorable graph,
improving upon the work of Arora, Chlamtac and Charikar.
----------------------------------------------------------------------------