Layers and Matroids for the Traveling Salesman's Paths

DOI10.1016/J.ORL.2017.11.002MaRDI QIDQ6284614arXivFDO

Authors Frans Schalekamp, András Sebö, Vera Traub, Anke van Zuylen

Publication date 21 March 2017

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ORL.2017.11.002

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial optimization (90C27)

arXiv classification

cs.DMmath.CO

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.

This page was built for publication: Layers and Matroids for the Traveling Salesman's Paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284614)