Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7543912 | Operations Research Letters | 2018 | 4 Pages |
Abstract
Gottschalk and Vygen proved that every solution of the subtour elimination linear program for traveling salesman paths is a convex combination of more and more restrictive “generalized Gao-trees”. We give a short proof of this fact, as a layered convex combination of bases of a sequence of increasingly restrictive matroids. A strongly polynomial, combinatorial algorithm follows for finding this convex combination, which is a new tool offering polyhedral insight, already instrumental in recent results for the sât path TSP.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Frans Schalekamp, András SebÅ, Vera Traub, Anke van Zuylen,