Some 0/1 polytopes need exponential size extended formulations
We prove that there are 0/1 polytopes P⊆R[superscript n] that do not admit a compact LP formulation. More precisely we show that for every n there is a set X⊆{0,1}[superscript n] such that conv(X) must have extension complexity at least 2[superscript n/2⋅(1−o(1)] . In other words, every polyhed...
Main Author: | Rothvoss, Thomas |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Mathematics |
Format: | Article |
Language: | English |
Published: |
Springer Berlin Heidelberg
2016
|
Online Access: | http://hdl.handle.net/1721.1/104664 |
Similar Items
-
Extended Formulations for Polygons
by: Fiorini, Samuel, et al.
Published: (2017) -
Some Properties of Metric Polytope Constraints
by: V. A. Bondarenko, et al.
Published: (2014-08-01) -
Gelfand―Tsetlin Polytopes and Feigin―Fourier―Littelmann―Vinberg Polytopes as Marked Poset Polytopes
by: Federico Ardila, et al.
Published: (2011-01-01) -
On q-integrals over order polytopes (extended abstract)
by: Jang Soo Kim
Published: (2020-04-01) -
Triangulations of root polytopes and reduced forms (Extended abstract)
by: Karola Mészáros
Published: (2009-01-01)