Non-Local Analysis of SDP-Based Approximation Algorithms (thesis)

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(n^0.2130) as opposed to the original O(n^0.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(n^0.2072)-coloring.

As an additional application of this approach, in 3-uniform hypergraphs containing an independent set of size gamma*n (for any constant gamma>0), we describe an algorithm which finds an independent set of size n^(Omega(gamma^2)) using the Theta(1/gamma^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.