Integrality Gaps for Sherali-Adams Relaxations

COMPUTER SCIENCE/DISCRETE MATH I
Topic:Integrality Gaps for Sherali-Adams Relaxations
Speaker:Yury Makarychev
Affiliation:Microsoft Research
Date:Monday, February 18
Time/Room:11:15am - 12:15pm/S-101

We prove strong lower bounds for Sherali-Adams relaxations of the MAX CUT, Vertex Cover and Sparsest Cut problems. Specifically, we show that the integrality gap of MAX CUT and Vertex Cover relaxations is 2-$\epsilon$ after n^delta rounds (where delta depends on epsilon); the integrality gap of Sparsest Cut is at least $C \max(\sqrt{\log n / (\log r + \log \log n)}$, $\log n / (r + \log \log n))$. Joint work with Moses Charikar and Konstantin Makarychev.