TIME: 1:30-2:20 pm,  November 21, 2006

PLACE: CSE 403

TITLE: New Approximation Guarantee for Chromatic Number

SPEAKER: Eden Chlamtac
         Princeton University
 

ABSTRACT:

We describe an algorithm which colors any 3-colorable graph using 
O(n^0.2074) colors, thus improving the algorithms of Karger, Motwani and 
Sudan, and Blum and Karger from almost a decade ago. The previous best 
known algorithm used O(n^3/14) colors. We build on these results, which 
combined semidefinite programming (SDP) relaxations (specifically, vector 
chromatic number) with some combinatorial techniques. We demonstrate a 
better relation between vector chromatic number and true chromatic number. 
While this already gives some improvement, we obtain our best result by 
working with stronger SDP relaxations (e.g. by adding "odd-cycle 
constraints"). Our analysis uses new geometric ideas inspired by the 
recent work of Arora, Rao and Vazirani.

This is joint work with Sanjeev Arora and Moses Charikar.