Extension complexity - Revision history

Citation bot: Added isbn. | Use this bot. Report bugs. | Suggested by Dominic3203 | #UCB_webform 6/8

2024-09-13T03:51:03Z

Added isbn. | Use this bot. Report bugs. | Suggested by Dominic3203 | #UCB_webform 6/8

← Previous revision		Revision as of 03:51, 13 September 2024
Line 124:		Line 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 = 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		\| title-link = Symposium on Theory of Computing
	\| year = 2015\| ~~s2cid~~ = ~~14438019~~		\| year = 2015\| isbn = 978-1-4503-3536-2
			\| s2cid = 14438019
	}}</ref>		}}</ref>

Dedhert.Jr: geometry-stub

2024-05-13T16:19:15Z

geometry-stub

← Previous revision		Revision as of 16:19, 13 May 2024
Line 145:		Line 145:


	{{~~math~~-stub}}		{{geometry-stub}}

Sir Ibee: Open access status updates in citations with OAbot #oabot

2024-01-11T06:44:19Z

Open access status updates in citations with OAbot #oabot

← Previous revision		Revision as of 06:44, 11 January 2024
Line 84:		Line 84:
	\| volume = 204		\| volume = 204
	\| year = 2013\| s2cid = 254236751		\| year = 2013\| s2cid = 254236751
			\| citeseerx = 10.1.1.483.9715
	}}</ref>		}}</ref>

OAbot: Open access bot: arxiv updated in citation with #oabot.

2024-01-06T00:27:38Z

Open access bot: arxiv updated in citation with #oabot.

← Previous revision		Revision as of 00:27, 6 January 2024
Line 58:		Line 58:
	\| year = 2015\| s2cid = 254144689		\| year = 2015\| s2cid = 254144689
	\| url = https://ir.cwi.nl/pub/24053		\| url = https://ir.cwi.nl/pub/24053
			\| arxiv = 1305.3268
	}}</ref>		}}</ref>

Citation bot: Add: url, s2cid, pages, volume. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1588/2500

2023-12-09T10:12:11Z

Add: url, s2cid, pages, volume. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1588/2500

← Previous revision		Revision as of 10:12, 9 December 2023
Line 17:		Line 17:
	\| doi = 10.1287/moor.2021.1137		\| doi = 10.1287/moor.2021.1137
	\| journal = [[Mathematics of Operations Research]]		\| journal = [[Mathematics of Operations Research]]
	\| title = Regular matroids have polynomial extension complexity~~}}</ref>~~		\| title = Regular matroids have polynomial extension complexity\| volume = 47
			\| pages = 540–559
			\| s2cid = 202660764
			}}</ref>

	<ref name=at>{{citation		<ref name=at>{{citation
Line 30:		Line 33:
	\| title = On the extension complexity of combinatorial polytopes		\| title = On the extension complexity of combinatorial polytopes
	\| volume = 153		\| volume = 153
	\| year = 2015}}</ref>		\| year = 2015\| s2cid = 254143169 }}</ref>

	<ref name=balas>{{citation		<ref name=balas>{{citation
Line 40:		Line 43:
	\| title = Projection, lifting and extended formulation in integer and combinatorial optimization		\| title = Projection, lifting and extended formulation in integer and combinatorial optimization
	\| volume = 140		\| volume = 140
	\| year = 2005}}</ref>		\| year = 2005\| s2cid = 18252683 }}</ref>

	<ref name=bdk>{{citation		<ref name=bdk>{{citation
Line 53:		Line 56:
	\| title = On the existence of 0/1 polytopes with high semidefinite extension complexity		\| title = On the existence of 0/1 polytopes with high semidefinite extension complexity
	\| volume = 153		\| volume = 153
	\| year = 2015~~}}</ref>~~		\| year = 2015\| s2cid = 254144689
			\| url = https://ir.cwi.nl/pub/24053
			}}</ref>

	<ref name=btn>{{citation		<ref name=btn>{{citation
Line 77:		Line 82:
	\| title = Extended formulations in combinatorial optimization		\| title = Extended formulations in combinatorial optimization
	\| volume = 204		\| volume = 204
	\| year = 2013~~}}</ref>~~		\| year = 2013\| s2cid = 254236751
			}}</ref>

	<ref name=frt>{{citation		<ref name=frt>{{citation
Line 91:		Line 97:
	\| title = Extended formulations for polygons		\| title = Extended formulations for polygons
	\| volume = 48		\| volume = 48
	\| year = 2012~~}}</ref>~~		\| year = 2012\| s2cid = 254032514
			}}</ref>

	<ref name=kaibel>{{citation		<ref name=kaibel>{{citation
Line 115:		Line 122:
	\| title = Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015		\| 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		\| title-link = Symposium on Theory of Computing
	\| year = 2015~~}}</ref>~~		\| year = 2015\| s2cid = 14438019
			}}</ref>

	<ref name=rothvoss>{{citation		<ref name=rothvoss>{{citation
Line 127:		Line 135:
	\| title = The matching polytope has exponential extension complexity		\| title = The matching polytope has exponential extension complexity
	\| volume = 64		\| volume = 64
	\| year = 2017~~}}</ref>~~		\| year = 2017\| s2cid = 47045361
			}}</ref>

	}}		}}

Chongkian: stub template should be placed at the very end of article after external link, navbox & category tags per WP:STUBSPACING

2023-10-18T15:59:00Z

stub template should be placed at the very end of article after external link, navbox & category tags per WP:STUBSPACING

← Previous revision		Revision as of 15:59, 18 October 2023
Line 130:		Line 130:

	}}		}}
⚫	{{math-stub}}

	[[Category:Polyhedral combinatorics]]		[[Category:Polyhedral combinatorics]]


		⚫	{{math-stub}}

Dedhert.Jr: math-stub

2023-05-27T06:26:03Z

math-stub

← Previous revision		Revision as of 06:26, 27 May 2023
Line 130:		Line 130:

	}}		}}
			{{math-stub}}

	[[Category:Polyhedral combinatorics]]		[[Category:Polyhedral combinatorics]]

35.3.99.193: fixed a (presumed) typo in first sentence.

2023-01-19T16:47:49Z

fixed a (presumed) typo in first sentence.

← Previous revision		Revision as of 16:47, 19 January 2023
Line 1:		Line 1:
	In [[convex geometry]] and [[polyhedral combinatorics]], the '''extension complexity''' is 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}}		In [[convex geometry]] and [[polyhedral combinatorics]], the '''extension complexity''' of 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}}		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}}

David Eppstein: New article

2021-09-04T07:12:46Z

New article

New page

In [[convex geometry]] and [[polyhedral combinatorics]], the '''extension complexity''' is 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}}

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 [[Matroid polytope|independence polytope]] of [[regular matroid]]s 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 [[Spectrahedron|spectrahedra]] in place of projections of polytopes.{{r|bdk|lrs}}

==References==
{{reflist|refs=

<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}}</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}}</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}}</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}}</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}}</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}}</ref>

<ref name=kaibel>{{citation
| last = Kaibel | first = Volker
| arxiv = 1104.1023
| journal = [[Optima (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}}</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}}</ref>

}}

[[Category:Polyhedral combinatorics]]