[Colloquium] TTIC Talk: Grant Schoenebeck, UC Berkeley

[Julia MacGlashan]

*REMINDER*

When:             *Wednesday, Feb 10 @ 11:00am*

Where:           * TTI-C Conference Room #526*, 6045 S Kenwood Ave


Who:              * **Grant Schoenebeck*, UC Berkeley


Title:          *      **Understanding the Limitations of Linear and
Semidefinite Programming*



 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.

Host:              Julia Chuzhoy, cjulia at ttic.edu*
*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100209/2343ccf6/attachment.htm