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.


  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 Canadian 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.