Volker Kaibel
University of Magdeburg, Germany
Abstract: The polytopes that seem to be associated naturally with combinatorial optimization problems tend to have rather complicated linear descriptions. However, in some cases there are very simple, nice, and easy to handle extended formulations for such polytopes, i.e., linear descriptions of higher dimensional polyhedra that can be projected linearly to the polytopes of interest. In this lecture, we discuss some aspects of this approach that has attracted quite some attention recently. Besides introducing the concept, we present some selected examples of extended formulations in particular meant to overview some techniques for their construction, and we discuss fundamental limitations of the approach, where we mainly concentrate on combinatorial obstructions that sometimes prevent the existance of small extended formulations.
The talk is based on joint papers with Samuel Fiorini, Dirk O. Theis, and Kanstantsin Pashkovich.