Speaker: Konstantinos Georgio, University of Waterloo
Title: Lift-and-project systems for combinatorial optimization problems; More than a decade of fascinating positive and negative results
A popular paradigm in approximation algorithms for intractable combinatorial optimization problems is to first formulate the problem at hand as an integer program and then relax the integrality condition, giving rise to a tractable optimization problem. At the same time, the relaxation introduces discrepancy between the true optimum and the optimal solution of the relaxation, which can be properly quantified so as to correspond to the approximability one can achieve for the combinatorial problem. In order to cope with this discrepancy, a number of systematic procedures, known as lift and-project systems, have been introduced that effectively tighten the relaxations and that enjoy appealing algorithmic properties.
Over the last decade, numerous positive and negative results have been established for lift-and project systems and for various intractable optimization problems. On one hand, the best algorithms known for a series of optimization problems are due to lift-and-project systems. On the other hand, there is evidence that the limitations of lift-and-project systems as tools in approximation algorithms indicate the actual hardness for a number of intractable optimization problems.
In this talk I will review the area of lift-and-project systems. After a self-contained and high level introduction to the systems, I will discuss a number of applications, trying to distill the main ingredients of this algorithmic tool. At the same time I will try to expose its weaknesses along with the challenges that are involved in showing positive and negative results. The exposition will be based on numerous fascinating results of the last decade or so.
More information on the lecture can be found HERE