Reducing Path TSP to TSP
From MaRDI portal
Recommendations
- Reducing path TSP to TSP
- A 1.5-approximation for path TSP
- Path-reduced costs for eliminating arcs in routing and scheduling
- Reduction of route optimization problems
- Improving Christofides' algorithm for the s-t path TSP
- Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
- scientific article; zbMATH DE number 2196172
- Edge elimination in TSP instances
- Approaching 3/2 for the \(s\)-\(t\)-path TSP
- Generalized traveling salesman problem reduction algorithms
Cites work
- scientific article; zbMATH DE number 1003253 (Why is no real title available?)
- scientific article; zbMATH DE number 3746840 (Why is no real title available?)
- A 1.5-approximation for path TSP
- A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
- A Randomized Rounding Approach to the Traveling Salesman Problem
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A new dynamic programming approach for spanning trees with chain constraints and beyond
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- An application of simultaneous diophantine approximation in combinatorial optimization
- An improved approximation algorithm for TSP in the half integral case
- An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Approaching 3/2 for the \(s\)-\(t\)-path TSP
- Approximating minimum-cost connected \(T\)-joins
- Approximation Algorithms for Orienteering and Discounted-Reward TSP
- Better \(s-t\)-tours by Gao trees
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Combinatorial optimization. Theory and algorithms
- Eight-fifth approximation for the path TSP
- Geometric algorithms and combinatorial optimization.
- How to tidy up a symmetric set-system by use of uncrossing operations
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- Improving Christofides' algorithm for the s-t path TSP
- Improving on best-of-many-Christofides for \(T\)-tours
- Integer programming and algorithmic geometry of numbers
- New inapproximability bounds for TSP
- Potentials in Undirected Graphs and Planar Multiflows
- Reassembling trees for the traveling salesman
- Removing and adding edges for the traveling salesman problem
- 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
- The Traveling Salesman Problem with Distances One and Two
- The salesman's improved paths through forests
- \(\frac{13}{9}\)-approximation for graphic TSP
Cited in
(6)- Multidepot capacitated vehicle routing with improved approximation guarantees
- Computing Hamiltonian paths with partial order restrictions
- Improved approximation algorithms for multidepot capacitated vehicle routing
- A better-than-1.6-approximation for prize-collecting TSP
- A better-than-1.6-approximation for prize-collecting TSP
- Better approximation algorithms for clustered TSP and subgroup planning
This page was built for publication: Reducing Path TSP to TSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5860476)
