Layers and Matroids for the Traveling Salesman's Paths
2017
Gottschalk and Vygen proved that every solution of the well-known subtour elimination linear program for traveling salesman paths is a convex combination of a set of more and more restrictive "generalized Gao trees" of the underlying graph. In this paper we give a short proof of this, as a {\em layered} convex combination of bases of a sequence of more and more restrictive matroids.
Our proof implies (via the matroid partition theorem) a strongly-polynomial combinatorial algorithm for finding this convex combination.
This is a new connection of the TSP to matroids, offering also a new polyhedral insight.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
6
References
1
Citations
NaN
KQI