TIME: 1:30-2:20 pm,  April 22, 2008

PLACE: CSE 503  

SPEAKER: Konstantin Makarychev

TITLE: Integrality Gaps for Sherali-Adams Relaxations

ABSTRACT:

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 Yury Makarychev.