Years ago, I spent a very pleasant couple of weeks in a group debunking a claimed linear programming formulation of the Traveling Salesman Problem. I wrote on this before, and bewailed the fact that I was not smart enough to figure out there was a general theorem there: Yannakakis showed that no symmetric linear programming formulation of polynomial size can formulate the TSP. The “symmetric” part of the theorem was always bothersome since it seemed an unnecessary addition. You can make a symmetric formulation “unsymmetric” by doing something goofy in adding a useless variable or similar, but the fundamental result still holds. Can asymmetry work on a fundamental level? I worked on trying to remove the symmetric assumption, but had no success. That’s not surprising since Yannakakis clearly would have not included the requirement if it was easy to remove. Yannakakis is smarter than Trick. Therefore Trick cannot remove the requirement. Q.E.D. But I still tried for a while.
Fortunately, research moves on, and people learn more and more, and finally enough gets proved that smart people can figure out how to move forward. It appears that the symmetric requirement can be removed. Sebastian Pokutta, and his coauthors Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronal de Wolf have a paper that proves that any linear programming formulation (symmetric or not) of the TSP is
exponentially sized super polynomial. Sebastian’s blog post has a very nice description of some recent history (including the astonishing result that sometimes the symmetry requirement does matter) and gives pointers to both the paper and to some slides. I have not had time to go through things thoroughly (or at all, really) but the paper seems a trove of interesting results. I feel like starting a Ph.D. seminar next week to study it!
Between Bill Cook’s soon-to-be-released TSP book and this news, 2012 is shaping up to the be the year of the Traveling Salesman Problem!