Tutte seminar - Thomas RothvoB

Some 0/1 Polytopes need exponential size extended formulations

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}ⁿ 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.