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

gollark: Simple problems, solved in the most hilariously inelegant way.
gollark: golang_irl
gollark: How? Go's got no tagged unions or generics.
gollark: So they implemented a really poor replacement for optional types but it doesn't even work on everything.
gollark: I mean, as far as I'm aware basically any *pointery* type can be nil, which is... many of them?

References
  1. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.