Technion 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 programming. ---------------------------------------------------------- Visit our home page- <http://www.cs.technion.ac.il/~colloq> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Hadas Heier <heier@cs.technion.ac.il>