Extension of a polyhedron

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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.[citation needed]

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[edit]

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 notorious Matching Polytope[edit]

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.[1]) The answer to this question is '"no'", as Thomas Rothvoß has proven in an acclaimed paper at STOC 2014.[3]

References[edit]

  1. ^ a b Schrijver, A. (2003). Combinatorial Optimization -- Polyhedra and efficiency.
  2. ^ 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.
  3. ^ 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.