Friday, February 17, 2012 3:30 pm
-
4:30 pm
EST (GMT -05:00)
Some 0/1 Polytopes need exponential size extended formulations
Speaker: | Thomas RothvoB |
---|---|
Affiliation: | MIT |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
We prove that there are 0/1 polytopes P that do not admit a compact LP formulation. More precisely we show that for every n there is a set X ⊆ {0,1}n such that conv(X) must have extension complexity at least 2{n/2 * (1-o(1))}. In other words, every polyhedron Q that can be linearly projected on conv(X) must have exponentially many facets. In fact, the same result also applies if conv(X) is restricted to be a matroid polytope.
The paper is available under: Some 0/1 polytopes need exponential size extended formulations.