Extension complexity: Difference between revisions

Revision as of 07:12, 4 September 2021

Latest revision as of 03:51, 13 September 2024

(7 intermediate revisions by 6 users not shown)

Line 1:

In [[convex geometry]] and [[polyhedral combinatorics]], the '''extension complexity''' isof a [[convex polytope]] <math>P</math> is the smallest number of [[Facet (geometry)|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 polygon]]s 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}}

Line 17:

| doi = 10.1287/moor.2021.1137

| journal = [[Mathematics of Operations Research]]

| title = Regular matroids have polynomial extension complexity}}</ref>| volume = 47

| pages = 540–559

| s2cid = 202660764

}}</ref>

<ref name=at>{{citation

Line 30 ⟶ 33:

| title = On the extension complexity of combinatorial polytopes

| volume = 153

| year = 2015| s2cid = 254143169 }}</ref>

<ref name=balas>{{citation

Line 40 ⟶ 43:

| title = Projection, lifting and extended formulation in integer and combinatorial optimization

| volume = 140

| year = 2005| s2cid = 18252683 }}</ref>

<ref name=bdk>{{citation

Line 53 ⟶ 56:

| title = On the existence of 0/1 polytopes with high semidefinite extension complexity

| volume = 153

| year = 2015}}</ref>| s2cid = 254144689

| url = https://ir.cwi.nl/pub/24053

| arxiv = 1305.3268

}}</ref>

<ref name=btn>{{citation

Line 77 ⟶ 83:

| title = Extended formulations in combinatorial optimization

| volume = 204

| year = 2013}}</ref>| s2cid = 254236751

| citeseerx = 10.1.1.483.9715

}}</ref>

<ref name=frt>{{citation

Line 91 ⟶ 99:

| title = Extended formulations for polygons

| volume = 48

| year = 2012}}</ref>| s2cid = 254032514

}}</ref>

<ref name=kaibel>{{citation

Line 115 ⟶ 124:

| 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}}</ref>| isbn = 978-1-4503-3536-2

| s2cid = 14438019

}}</ref>

<ref name=rothvoss>{{citation

Line 127 ⟶ 138:

| title = The matching polytope has exponential extension complexity

| volume = 64

| year = 2017}}</ref>| s2cid = 47045361

}}</ref>

}}

[[Category:Polyhedral combinatorics]]

{{geometry-stub}}