Speaker: Moses Charikar Princeton University
Time: 2009-04-16 16:00-2009-04-16 17:00
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

Lift-and-project procedures are systematic techniques for strengthening mathematical programming relaxations of optimization problems. Determining whether the solutions to such lift-and-project relaxations can be used to obtain improved approximation algorithms is an interesting question. We show integrality gaps for Sherali-Adams lift-and-project relaxations for several optimization problems such as Max Cut, Vertex Cover, Maximum Acyclic Subgraph, Sparsest Cut and other problems.

The main combinatorial challenge in constructing these gap examples is the construction of a fractional solution that is far from an integer solution, but yet admits consistent distributions of local solutions for all small subsets of variables. Satisfying this consistency requirement is one of the major hurdles to constructing Sherali-Adams gap examples.

We present a modular recipe for achieving this, based on metrics with a local-global structure. Roughly speaking, such metrics have good local properties (every small subset embeds isometrically into l_1), yet exhibit poor global structure (i.e. a very high distortion is needed for embedding the entire metric into l_1). The talk will outline the construction of these local-global metrics and explain how they lead to integrality gaps for Sherali-Adams relaxations.

Joint work with Konstantin Makarychev and Yury Makarychev

Short Bio:

Moses Charikar is an Associate Professor of Computer Science at Princeton University. He received his B.Tech from IIT Bombay and his Ph.D. from Stanford University. He spent a year in the research group at Google and has been at Princeton since. His research interests are in algorithm design and analysis, particularly in approximation algorithms, the study of metric embeddings and algorithmic techniques for large data sets.