{"id":1587,"date":"2012-01-05T17:20:47","date_gmt":"2012-01-05T21:20:47","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1587"},"modified":"2012-01-05T17:20:47","modified_gmt":"2012-01-05T21:20:47","slug":"super-exciting-news-on-super-polynomiality-of-lp-formulations-of-the-tsp-polytope","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2012\/01\/05\/super-exciting-news-on-super-polynomiality-of-lp-formulations-of-the-tsp-polytope\/","title":{"rendered":"Super Exciting News on Super Polynomiality of LP Formulations of the TSP Polytope"},"content":{"rendered":"

Years ago, I spent a very pleasant couple of weeks in a group debunking a claimed linear programming formulation of the Traveling Salesman Problem.\u00a0 I wrote on this before<\/a>, and bewailed the fact that I was not smart enough to figure out there was a general theorem there:\u00a0\u00a0Yannakakis showed that no symmetric linear programming formulation of polynomial size can formulate the TSP.\u00a0 The “symmetric” part of the theorem was always bothersome since it seemed an unnecessary addition.\u00a0 You can make a symmetric formulation “unsymmetric” by doing something goofy in adding a useless variable or similar, but the fundamental result still holds. \u00a0 Can asymmetry work on a fundamental level? I worked on trying to remove the symmetric assumption, but had no success.\u00a0 That’s not surprising since Yannakakis clearly would have not included the requirement if it was easy to remove.\u00a0 Yannakakis is smarter than Trick.\u00a0 Therefore Trick cannot remove the requirement.\u00a0 Q.E.D.\u00a0 But I still tried for a while.<\/p>\n

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. \u00a0 It appears that the symmetric requirement can be removed.\u00a0 Sebastian Pokutta<\/a>, and his coauthors Samuel Fiorini<\/a>, Serge Massar<\/a>, Hans Raj Tiwary<\/a>, and Ronal de Wolf<\/a> have a paper that proves that any linear programming formulation (symmetric or not) of the TSP is exponentially sized <\/del>super polynomial.\u00a0 Sebastian’s blog post<\/a> 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.\u00a0 I have not had time to go through things thoroughly (or at all, really) but the paper seems a trove of interesting results.\u00a0 I feel like starting a Ph.D. seminar next week to study it!<\/p>\n

Between Bill Cook’s soon-to-be-released TSP book<\/a> and this news, 2012 is shaping up to the be the year of the Traveling Salesman Problem!<\/p>\n","protected":false},"excerpt":{"rendered":"

Years ago, I spent a very pleasant couple of weeks in a group debunking a claimed linear programming formulation of the Traveling Salesman Problem.\u00a0 I wrote on this before, and bewailed the fact that I was not smart enough to figure out there was a general theorem there:\u00a0\u00a0Yannakakis showed that no symmetric linear programming formulation … Continue reading “Super Exciting News on Super Polynomiality of LP Formulations of the TSP Polytope”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,46],"tags":[],"class_list":["post-1587","post","type-post","status-publish","format-standard","hentry","category-blogs-and-web","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1587","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1587"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1587\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1587"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1587"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}