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


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.


Talk 1 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. If you have already decided to take Generic Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.