Exponential Lower Bounds for Polytopes in Combinatorial Optimization: The TSP Polytope Has Extension Complexity 2^Ω(√n)Research Paper
Combinatorial optimization problems are routinely solved by writing the convex hull of their feasible solutions as the feasible region of a linear program. When that convex hull has exponentially many facets, a classical trick is to add auxiliary variables: a polytope with many facets may be the linear projection of a higher-dimensional polyhedron with few.…