On linear programming formulations of the TSP polytope

ACO Student Seminar
Friday, November 16, 2012 - 13:00
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech, ISyE
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)