Thursday, Nov 1, 2:15pm, WWH-1314
SPEAKER:
Madhur Tulsiani, UC-Berkeley
TITLE:
Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex
Cover and Max Cut
ABSTRACT:
Lovasz and Schrijver define hierarchies of operators, which act on
simple linear programs to produce stronger linear programming (LP)
and semidefinite programming (SDP) relaxations for optimization
problems. A constant number of applications (rounds) of these
operators are known to capture most knowm LP/SDP based
approximation algorithms.
We prove integrality gaps for these hierarchies when applied to the
basic LP relaxation for Vertex Cover. We show even after \Omega(n)
applications of these operators the integrality gap remains at least
2-\epsilon in the hierarchy of LPs (called LS) and at least
7/6-\epsilon in the hierarchy of SDPs (called LS+). Since r rounds
take time n^{O(r)} to solve, this gives lower bounds even for
exponential time algorithms based on programs within these
hierarchies. This is joint work with Grant Schoenebeck and Luca
Trevisan.
------------------------------------------------------------------------