Computer Science Colloquium
Time+Place : Thursday 22/12/2011 14:30 room 337-8 Taub  Bld.
Speaker    : Eden Chlamtac
Affiliation: Tel-Aviv University
Host       : Seffi Naor
Title      : Convex Programming Hierarchies: Trading Time for Approximation
Abstract   :
Linear programming (LP) and semidefinite programming (SDP) are powerful
convex optimization tools which have become ubiquitous in the field of
approximation algorithms in the last few decades. Given a combinatorial
optimization problem (e.g. Maximum Independent 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, 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.
Short Bio:
Eden Chlamtac received a B.Sc. in Mathematics and Computer Science from
Tel-Aviv University in 2001, an M.Sc. in Computer Science from the Weizmann
Institute of Science in 2003, and a PhD in Computer Science from Princeton
University in 2009 under the supervision of Sanjeev Arora. Since completing
his PhD, he was a postdoctoral fellow at the Weizmann Institute for two
years, at the University of Toronto for one semester, and is currently a
postdoctoral fellow at Tel Aviv University. His main research interest is in
the field of approximation algorithms, especially those that use convex
Visit our home page-   <>
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>