Lower Bounds for Approximating MAX-CUT and Sparsest Cut
Speaker: Subhash Khot , Georgia Institute of Technology
Date: May 16 2006
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Madhu Sudan, Massachusetts Institute of Technology
Contact: Kevin Matulef, 3-5883, matulef@mit.edu
Relevant URL: http://theory.csail.mit.edu/toc-seminars/Goemans and Williamson, in their seminal 1994 paper, introduced the use of semi-definite programming as an algorithmic tool. Using a natural SDP-relaxation and a rounding procedure, they obtained 0.878... approximation to MAX-CUT problem. Since then, the technique has found several applications including the recent breakthrough result of Arora, Rao and Vazirani that gave O(sqrt{log n}) approximation to the Sparsest Cut problem.
I will talk about recent results proving lower bounds on the approximability of MAX-CUT and Sparsest Cut. These lower bounds are of two types: firstly, hardness of approximation results assuming the Unique Games Conjecture and secondly, unconditional and explicit intergrality gaps for the SDP relaxations (even with so-called triangle inequality constraints). The lower bound for MAX-CUT matches exactly with the Goemans-Williamson's bound. The integrality gap result for Sparsest Cut disproves a conjecture of Goemans and Linial that the negative type metrics embed into L_1 with constant distortion.
Based on joint works with [Guy Kindler, Elchanan Mossel and Ryan O'Donnell], [Nisheeth Vishnoi] and [Nikhil Devanur, Rishi Saket and Nisheeth Vishnoi].
See other events that are part of Theory Colloquium Spring 2006
See other events happening in May 2006
