In convex geometry and polyhedral combinatorics, the '''extension complexity''' of a convex polytope <math>P</math> is the smallest number of facets among convex polytopes <math>Q</math> that have <math>P</math> as a projection. In this context, <math>Q</math> is called an '''extended formulation''' of <math>P</math>; it may have much higher dimension than <math>P</math>.{{r|balas|kaibel|ccz}}
The extension complexity depends on the precise shape of <math>P</math>, not just on its combinatorial structure. For instance, regular polygons with <math>n</math> sides have extension complexity <math>O(\log n)</math> (expressed using big O notation),{{r|btn|frt}} but some other convex <math>n</math>-gons have extension complexity at least proportional to <math>\sqrt{n}</math>.{{r|frt}}
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.{{r|at}} For instance, it is known that the matching polytope has exponential extension complexity.{{r|rothvoss}} On the other hand, the independence polytope of regular matroids has polynomial extension complexity.{{r|af}}
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.{{r|bdk|lrs}}
==References== <references>
<ref name=af>{{citation | last1 = Aprile | first1 = Manuel | last2 = Fiorini | first2 = Samuel | arxiv = 1909.08539 | date = July 2021 | doi = 10.1287/moor.2021.1137 | journal = Mathematics of Operations Research | title = Regular matroids have polynomial extension complexity| volume = 47 | pages = 540–559 | s2cid = 202660764 }}</ref>
<ref name=at>{{citation | last1 = Avis | first1 = David | author1-link = David Avis | last2 = Tiwary | first2 = Hans Raj | arxiv = 1302.2340 | doi = 10.1007/s10107-014-0764-2 | issue = 1, Ser. B | journal = Mathematical Programming | mr = 3395543 | pages = 95–115 | title = On the extension complexity of combinatorial polytopes | volume = 153 | year = 2015| s2cid = 254143169 }}</ref>
<ref name=balas>{{citation | last = Balas | first = Egon | author-link = Egon Balas | doi = 10.1007/s10479-005-3969-1 | journal = Annals of Operations Research | mr = 2194735 | pages = 125–161 | title = Projection, lifting and extended formulation in integer and combinatorial optimization | volume = 140 | year = 2005| s2cid = 18252683 }}</ref>
<ref name=bdk>{{citation | last1 = Briët | first1 = Jop | last2 = Dadush | first2 = Daniel | last3 = Pokutta | first3 = Sebastian | doi = 10.1007/s10107-014-0785-x | issue = 1, Ser. B | journal = Mathematical Programming | mr = 3395546 | pages = 179–199 | title = On the existence of 0/1 polytopes with high semidefinite extension complexity | volume = 153 | year = 2015| s2cid = 254144689 | url = https://ir.cwi.nl/pub/24053 | arxiv = 1305.3268 }}</ref>
<ref name=btn>{{citation | last1 = Ben-Tal | first1 = Aharon | last2 = Nemirovski | first2 = Arkadi | author2-link = Arkadi Nemirovski | doi = 10.1287/moor.26.2.193.10561 | issue = 2 | journal = Mathematics of Operations Research | mr = 1895823 | pages = 193–205 | title = On polyhedral approximations of the second-order cone | volume = 26 | year = 2001}}</ref>
<ref name=ccz>{{citation | last1 = Conforti | first1 = Michele | last2 = Cornuéjols | first2 = Gérard | author2-link = Gérard Cornuéjols | last3 = Zambelli | first3 = Giacomo | doi = 10.1007/s10479-012-1269-0 | journal = Annals of Operations Research | mr = 3039264 | pages = 97–143 | title = Extended formulations in combinatorial optimization | volume = 204 | year = 2013| s2cid = 254236751 | citeseerx = 10.1.1.483.9715 }}</ref>
<ref name=frt>{{citation | last1 = Fiorini | first1 = Samuel | last2 = Rothvoß | first2 = Thomas | last3 = Tiwary | first3 = Hans Raj | arxiv = 1107.0371 | doi = 10.1007/s00454-012-9421-9 | issue = 3 | journal = Discrete & Computational Geometry | mr = 2957636 | pages = 658–668 | title = Extended formulations for polygons | volume = 48 | year = 2012| s2cid = 254032514 }}</ref>
<ref name=kaibel>{{citation | last = Kaibel | first = Volker | arxiv = 1104.1023 | journal = Optima | pages = 2–7 | title = Extended formulations in combinatorial optimization | volume = 85 | year = 2011}}</ref>
<ref name=lrs>{{citation | last1 = Lee | first1 = James R. | last2 = Raghavendra | first2 = Prasad | last3 = Steurer | first3 = David | editor1-last = Servedio | editor1-first = Rocco A. | editor2-last = Rubinfeld | editor2-first = Ronitt | editor2-link = Ronitt Rubinfeld | arxiv = 1411.6317 | contribution = Lower bounds on the size of semidefinite programming relaxations | doi = 10.1145/2746539.2746599 | pages = 567–576 | publisher = Association for Computing Machinery | title = Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 | title-link = Symposium on Theory of Computing | year = 2015| isbn = 978-1-4503-3536-2 | s2cid = 14438019 }}</ref>
<ref name=rothvoss>{{citation | last = Rothvoß | first = Thomas | arxiv = 1311.2369 | doi = 10.1145/3127497 | issue = 6 | journal = Journal of the ACM | mr = 3713797 | page = A41:1–A41:19 | title = The matching polytope has exponential extension complexity | volume = 64 | year = 2017| s2cid = 47045361 }}</ref>
</references>
Category:Polyhedral combinatorics
{{geometry-stub}}