Reducing Path TSP to TSP
From MaRDI portal
Publication:5860476
DOI10.1137/20M135594XOpenAlexW3205213369MaRDI QIDQ5860476
Rico Zenklusen, Vera Traub, Jens Vygen
Publication date: 19 November 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m135594x
Cites Work
- Unnamed Item
- 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
- New inapproximability bounds for TSP
- A factor 2 approximation algorithm for the generalized Steiner network problem
- An application of simultaneous diophantine approximation in combinatorial optimization
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Geometric algorithms and combinatorial optimization.
- How to tidy up a symmetric set-system by use of uncrossing operations
- Better \(s-t\)-tours by Gao trees
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- \(\frac{13}{9}\)-approximation for graphic TSP
- An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
- Approximating minimum-cost connected \(T\)-joins
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- Improving on best-of-many-Christofides for \(T\)-tours
- A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots
- Reassembling Trees for the Traveling Salesman
- Improving Christofides' Algorithm for the s-t Path TSP
- Removing and Adding Edges for the Traveling Salesman Problem
- Integer Programming and Algorithmic Geometry of Numbers
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- Potentials in Undirected Graphs and Planar Multiflows
- The Traveling Salesman Problem with Distances One and Two
- Eight-Fifth Approximation for the Path TSP
- An improved approximation algorithm for TSP in the half integral case
- The Salesman’s Improved Paths through Forests
- A 1.5-Approximation for Path TSP
- A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond
- Approaching 3/2 for the s - t -path TSP
- Approximation Algorithms for Orienteering and Discounted-Reward TSP
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Combinatorial optimization. Theory and algorithms
This page was built for publication: Reducing Path TSP to TSP
