Layers and matroids for the traveling salesman’s paths
2018
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 s − t path TSP.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
8
References
8
Citations
NaN
KQI