Lesson plan
Extension complexity
In convex geometry and polyhedral combinatorics, the extension complexity of a convex polytope P is the smallest number of facets among convex polytopes Q that have P as a projection. In this context, Q is called an extended formulation of P ; it may have much higher dimension than P . The extension complexity depends on the precise shape of P , not just on its combinatorial structure. For instance, regular polygons with n sides have extension complexity O(\log n) (expressed using big O notation), but some other convex n -gons have extension complexity at least proportional to \sqrt{n} . If a polytope describing the feasible solutions to a combinatorial optimization problem has low extension complexity, this could potentially be used to devise efficient algorithms for the problem, using linear programming on its extended formulation. For this reason, researchers have studied the extension complexity of the polytopes arising in this way. For instance, it is known that the matching polytope has exponential extension complexity. On the other hand, the independence polytope of regular matroids has polynomial extension complexity. The notion of extension complexity has also been generalized from linear programming to semidefinite programming, by considering projections of spectrahedra in place of projections of polytopes.
Article summary
In convex geometry and polyhedral combinatorics, the extension complexity of a convex polytope P is the smallest number of facets among convex polytopes Q that have P as a projection. In this context, Q is called an extended formulation of P ; it may have much higher dimension than P . The extension complexity depends on the precise shape of P , not just on its combinatorial structure. For instance, regular polygons with n sides have extension complexity O(\log n) (expressed using big O notation), but some other convex n -gons have extension complexity at least proportional to \sqrt{n} . If a polytope describing the feasible solutions to a combinatorial optimization problem has low extension complexity, this could potentially be used to devise efficient algorithms for the problem, using linear programming on its extended formulation. For this reason, researchers have studied the extension complexity of the polytopes arising in this way. For instance, it is known that the matching polytope has exponential extension complexity. On the other hand, the independence polytope of regular matroids has polynomial extension complexity. The notion of extension complexity has also been generalized from linear programming to semidefinite programming, by considering projections of spectrahedra in place of projections of polytopes.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.