Layers and matroids for the traveling salesman's paths

DOI10.1016/j.orl.2017.11.002OpenAlexW4301322391MaRDI QIDQ2417048

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

Publication date: 11 June 2019

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.07170

zbMATH Keywords

polyhedraapproximation algorithmspanning treematroid partitionChristofides' heuristicpath traveling salesman problem (TSP)

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items (3)

Improving on best-of-many-Christofides for \(T\)-tours ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP

Cites Work

• Unnamed Item
• Testing membership in matroid polyhedra
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• Improving Christofides' Algorithm for the s-t Path TSP
• Better s-t-Tours by Gao Trees
• Approaching $\frac{3}{2}$ for the $s$-$t$-path TSP

This page was built for publication: Layers and matroids for the traveling salesman's paths