Article ID Journal Published Year Pages File Type
7543912 Operations Research Letters 2018 4 Pages PDF
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
, , , ,