Technion, IEM faculty - Bi-weekly Faculty Workshop
 
Speaker: Eden Chlamtac
 
Title: Convex Programming Hierarchies: Trading Time for Approximation
 
Date: 04/12/2011
 
Time: 11:30
 
Place: Bloomfield-527
 
Abstract:  <http://ie.technion.ac.il/seminar_files/1322582330_eden.doc>
 
Or simply read this:
 
Convex optimization tools, such as linear programming (LP) and
semidefinite programming (SDP), have become ubiquitous in the field
of combinatorial approximation algorithms in the last few decades. Given
a combinatorial optimization problem (e.g. Maximum Stable Set), a
standard approach to obtain an approximation algorithm is as follows:
formulate the problem as an integer program (IP), relax this
formulation to an LP or SDP, solve the relaxation, and then "round"
the solution back to an integer solution.
 
This approach is limited by how well the convex program (LP or SDP)
approximates the original IP formulation, i.e. the integrality gap.
One way to circumvent this limitation is through hierarchies of
convex programs (so -called lift-and-project methods), which give a
systematic way of iteratively strengthening any relaxation (at the
cost of increased running time to solve it), so that the integrality
gap gradually decreases.
 
While initially, most of the literature on hierarchies in the context
of approximation algorithms had focused on impossibility results,
there has been a surprising surge of recent positive results. I will
survey this recent development, by describing a number of
combinatorial optimization problems for which we have been able to
achieve improved approximations using hierarchies.
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from:  <ehazan@ie.technion.ac.il>