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.
History
Historically, questions about extensions first surfaced in combinatorial optimization, where extensions arise naturally from extended formulations[1]
A seminal work by Yannakakis [2] connected extension complexity to various other notions in mathematics, in particular nonnegative rank of nonnegative matrices and communication complexity. The term extension was coined by Kaibel (cf. [3]).
The notorious Matching Polytope
Much of the research in the theory of extensions is 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.[4])
References
- ^ Schrijver, A. (2003). Combinatorial Optimization -- Polyhedra and efficiency.
- ^ Yannakakis, M. (1991). "Expressing combinatorial optimization problems by linear programs". J. Comput. System Sci. 43 (3): 441–466.
- ^ Cochran, J.J. (forthcoming). Wiley Encyclopedia of Operations Research and Management Science.
{{cite book}}: Check date values in:|year=(help)CS1 maint: year (link) - ^ Schrijver, A. (2003). Combinatorial Optimization -- Polyhedra and efficiency.