Extension of a polyhedron
In mathematics, in particular in the theory of polyhedra and polytopes, an extension of a polyhedron P is a polyhedron Q together with an affine or, more generally, projective map π mapping Q onto P.
Typically, given a polyhedron P, one asks what properties an extension of P must have. Of particular importance here is the extension complexity of P: the minimum number of facets of any polyhedron Q which participates in an extension of P.
The notorious Matching Polytope
Much of the research in the theory of extensions has been driven by a notorious problem about the Matching Polytope: Is the extension complexity of the convex hull of all matchings of a graph on n vertices bounded by a polynomial in n? (cf.) The answer to this question is '"no'", as Thomas Rothvoß has proven in an acclaimed paper at STOC 2014.
- Schrijver, A. (2003). Combinatorial Optimization -- Polyhedra and efficiency.
- Yannakakis, M. (1991). "Expressing combinatorial optimization problems by linear programs". J. Comput. Syst. Sci. 43 (3): 441–466. doi:10.1016/0022-0000(91)90024-y.
- Rothvoß, Thomas (2014). "The matching polytope has exponential extension complexity". Proceedings of the forty-sixth annual ACM symposium on Theory of computing. STOC 2014. New York: ACM. arXiv:1311.2369. Bibcode:2013arXiv1311.2369R.