Extended Formulations for Polygons
The extension complexity of a polytope P is the smallest integer k such that P is the projection of a polytope Q with k facets. We study the extension complexity of n-gons in the plane. First, we give a new proof that the extension complexity of regular n-gons is O(log n), a result originating from...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer-Verlag
2017
|
| Online Access: | http://hdl.handle.net/1721.1/107947 |
| _version_ | 1826212987193524224 |
|---|---|
| author | Fiorini, Samuel Tiwary, Hans Raj Rothvoss, Thomas |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Fiorini, Samuel Tiwary, Hans Raj Rothvoss, Thomas |
| author_sort | Fiorini, Samuel |
| collection | MIT |
| description | The extension complexity of a polytope P is the smallest integer k such that P is the projection of a polytope Q with k facets. We study the extension complexity of n-gons in the plane. First, we give a new proof that the extension complexity of regular n-gons is O(log n), a result originating from work by Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 193–205, 2001). Our proof easily generalizes to other permutahedra and simplifies proofs of recent results by Goemans (2009), and Kaibel and Pashkovich (2011). Second, we prove a lower bound of √(2n) on the extension complexity of generic n-gons. Finally, we prove that there exist n-gons whose vertices lie on an O(n)×O(n[superscript 2]) integer grid with extension complexity Ω(√/n./(√(log n))). |
| first_indexed | 2024-09-23T15:41:18Z |
| format | Article |
| id | mit-1721.1/107947 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:41:18Z |
| publishDate | 2017 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1079472022-09-29T15:32:18Z Extended Formulations for Polygons Fiorini, Samuel Tiwary, Hans Raj Rothvoss, Thomas Massachusetts Institute of Technology. Department of Mathematics Rothvoss, Thomas The extension complexity of a polytope P is the smallest integer k such that P is the projection of a polytope Q with k facets. We study the extension complexity of n-gons in the plane. First, we give a new proof that the extension complexity of regular n-gons is O(log n), a result originating from work by Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 193–205, 2001). Our proof easily generalizes to other permutahedra and simplifies proofs of recent results by Goemans (2009), and Kaibel and Pashkovich (2011). Second, we prove a lower bound of √(2n) on the extension complexity of generic n-gons. Finally, we prove that there exist n-gons whose vertices lie on an O(n)×O(n[superscript 2]) integer grid with extension complexity Ω(√/n./(√(log n))). Alexander von Humboldt-Stiftung. Feodor Lynen Postdoctoral Fellowship United States. Office of Naval Research (Grant N00014-11-1-0053) National Science Foundation (U.S.) (Contract CCF-08298780 2017-04-07T17:36:07Z 2017-04-07T17:36:07Z 2012-03 2012-02 2016-08-18T15:41:10Z Article http://purl.org/eprint/type/JournalArticle 0179-5376 1432-0444 http://hdl.handle.net/1721.1/107947 Fiorini, Samuel, Thomas Rothvoß, and Hans Raj Tiwary. “Extended Formulations for Polygons.” Discrete & Computational Geometry 48, no. 3 (March 16, 2012): 658–668. en http://dx.doi.org/10.1007/s00454-012-9421-9 Discrete & Computational Geometry Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Science+Business Media, LLC application/pdf Springer-Verlag Springer-Verlag |
| spellingShingle | Fiorini, Samuel Tiwary, Hans Raj Rothvoss, Thomas Extended Formulations for Polygons |
| title | Extended Formulations for Polygons |
| title_full | Extended Formulations for Polygons |
| title_fullStr | Extended Formulations for Polygons |
| title_full_unstemmed | Extended Formulations for Polygons |
| title_short | Extended Formulations for Polygons |
| title_sort | extended formulations for polygons |
| url | http://hdl.handle.net/1721.1/107947 |
| work_keys_str_mv | AT fiorinisamuel extendedformulationsforpolygons AT tiwaryhansraj extendedformulationsforpolygons AT rothvossthomas extendedformulationsforpolygons |