Title: Understanding the Limitations of Linear and Semidefinite Programming
Speaker: Grant Schoenebeck, Princeton University
Abstract:
Linear and Semidefinite programs provide the best
approximation algorithms for many NP-hard combinatorial optimization
problems. This talk will introduce recent techniques to give
unconditional lower bounds for algorithms based on Linear and
Semidefinite programs (LPs and SDPs, respectively). In particular, I
will define and give background about LP and SDP hierarchies, which
include a large class of SDPs and LPs including the most famous SDP
algorithms (which occur very low in the hierarchy). I will then
sketch two lower bounds for these hierarchies. The first result shows
that a large class of linear programs (generated by the
Lovasz-Schrijver hierarchy) requires exponential time to approximate
Vertex Cover to better than a factor of 2-epsilon. The second result
shows that a large class of semidefinite programs (generated by the
Lasserre hierarchy) requires exponential time to refute a random 3-XOR
instance (even though such an instance is very far from satisfiable).
As a corollary, the same class requires exponential time to
approximate Vertex Cover to better than a factor of 7/6-epsilon. This
result is the first construction of a Lasserre integrality gap, and
simplifies, strengthens, and helps to explain several previous
results.