Tuesday, 15:45 - 16:10 h, Room: H 3004


Thomas Rothvoss
Some 0/1 polytopes need exponential size extended formulations


We prove that there are 0/1 polytopes P ⊆ Rn 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 2n/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:, http://arxiv.org/abs/1105.0036


Talk 2 of the invited session Tue.3.H 3004
"Extended formulations in discrete optimization I" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.