Title: Understanding the Limitations of Linear and Semidefinite Programming
Speaker: Grant Schoenebeck, Princeton University
Date: Wednesday, March 23, 2011 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
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.