Improving on best-of-many-Christofides for \(T\)-tours
From MaRDI portal
Publication:2661569
DOI10.1016/j.orl.2020.09.009OpenAlexW3090361369MaRDI QIDQ2661569
Publication date: 7 April 2021
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2009.09743
Related Items (1)
Cites Work
- Unnamed Item
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- A construction for binary matroids
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Better \(s-t\)-tours by Gao trees
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
- Approximating minimum-cost connected \(T\)-joins
- Layers and matroids for the traveling salesman's paths
- Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP
- Reassembling Trees for the Traveling Salesman
- Improving Christofides' Algorithm for the s-t Path TSP
- Heuristic analysis, linear programming and branch and bound
- A new approach to the minimum cut problem
- Computing All Small Cuts in an Undirected Network
- Matching, Euler tours and the Chinese postman
- Eight-Fifth Approximation for the Path TSP
- Reducing path TSP to TSP
- Suboptimal cuts: Their enumeration, weight and number
- The Salesman’s Improved Paths through Forests
- A 1.5-Approximation for Path TSP
- Approaching 3/2 for the s - t -path TSP
- Minimum cuts in near-linear time
This page was built for publication: Improving on best-of-many-Christofides for \(T\)-tours
