On linear programming formulations of the TSP polytope

Series
ACO Student Seminar
Time
Friday, November 16, 2012 - 1:00pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Sebastian Pokutta – Georgia Tech, ISyE – http://www.pokutta.com
Organizer
Cristóbal Guzmán
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. (joint work with Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronald de Wolf)