2011/04/06 by Kaibel, Volker · 5 citations
#52B12 #90C10 #90C57 #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1104.1023
The concept of representing a polytope that is associated with some combinatorial optimization problem as a linear projection of a higher-dimensional polyhedron has recently received increasing attention. In this paper (written for the newsletter Optima of the Mathematical Optimization Society), we provide a brief introduction to this topic and sketch some of the recent developments with respect to both tools for constructing such extended formulations as well as lower bounds on their sizes.