Invited Session Tue.3.H 3004

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

Cluster 2: Combinatorial optimization [...]

Extended formulations in discrete optimization I


Chair: Samuel Fiorini and Gautier Stauffer



Tuesday, 15:15 - 15:40 h, Room: H 3004, Talk 1

Sebastian Pokutta
On linear programming formulations of the TSP polytope

Coauthors: Ronald de Wolf, Samuel Fiorini, Serge Massar, Hans-Raj Tiwary


We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.



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

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:,



Tuesday, 16:15 - 16:40 h, Room: H 3004, Talk 3

Roland Grappe
Extended formulations, non-negative factorizations, and randomized communication protocols

Coauthors: Yuri Faenza, Samuel Fiorini, Tiwary Hans Raj


We show that the binary logarithm of the non-negative rank of a non-negative matrix is, up to small constants, equal to the minimum complexity of a randomized communication protocol computing the matrix in expectation.
We use this connection to prove new conditional lower bounds on the sizes of extended formulations, in particular, for perfect matching polytopes.


  Online lending company provides a wide range of ways to get money by means of Tennessee Loans Online. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.