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: | |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
Springer Berlin Heidelberg
2016
|
Online Access: | http://hdl.handle.net/1721.1/104664 |