Some 0/1 polytopes need exponential size extended formulations

Details Some 0/1 polytopes need exponential size extended formulations Some 0/1 polytopes need exponential size extended formulations

2011-04-30

arxiv.org/abs/1105.0036v1

Mathematics

Combinatorics

Scientific paper

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 sets X \subseteq {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. Conditioning on NP not contained in P_{/poly}, our result rules out the existence of any compact formulation for the TSP polytope, even if the formulation may contain arbitrary real numbers.

Affiliated with

Also associated with

No associations

Rating

Some 0/1 polytopes need exponential size extended formulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some 0/1 polytopes need exponential size extended formulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some 0/1 polytopes need exponential size extended formulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-65611