3 ms·
On linear programming formulations for the TSP polytope
- cschmidt 15y agoThis paper is making some waves in Operations Research circles: 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. This argument is independent of the P-vs-NP argument, as it doesn't consider the encoding length of the coefficients.