conference paper
Lower Bounds on the Size of Semidefinite Programming Relaxations
James R. Leea, Prasad Raghavendrab, David Steurerc
- aUniversity of Washington, Seattle, WA, USA
- bUC Berkeley, Berkeley, CA, USA
- cCornell, Ithaca, NY, USA
Looking for the full paper…
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on n-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than 2nδ, for some constant δ > 0. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes.