Published on *Computer Science Department at Princeton University* (https://www.cs.princeton.edu)

Report ID:

TR-843-08

Authors:

Chlamtac, Eden [1]

Date:

October 2008

Pages:

106

Download Formats:

[PDF [2]]

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.

**Links**

[1] https://www.cs.princeton.edu/research/techreps/author/595

[2] ftp://ftp.cs.princeton.edu/techreports/2008/843.pdf