A 3/2-Approximation for the Metric Many-Visits Path TSP
From MaRDI portal
Recommendations
Cites work
- A (slightly) improved approximation algorithm for metric TSP
- A 1.5-approximation for path TSP
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- A Dynamic Programming Approach for Sequencing Groups of Identical Jobs
- A dynamic programming approach for the aircraft landing problem with aircraft classes
- A Dynamic Programming Approach to Sequencing Problems
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
- A strongly polynomial algorithm for the transportation problem
- A survey of scheduling problems with setup times or costs
- Algorithmic meta-theorems for restrictions of treewidth
- An improved approximation algorithm for ATSP
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Approaching 3/2 for the \(s\)-\(t\)-path TSP
- Approximating minimum bounded degree spanning trees to within one of optimal
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Better \(s-t\)-tours by Gao trees
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Computing All Small Cuts in an Undirected Network
- Connections in combinatorial optimization
- Degree bounded matroids and submodular flows
- Dynamic Programming Treatment of the Travelling Salesman Problem
- Eight-fifth approximation for the path TSP
- Empowering the configuration-IP -- new PTAS results for scheduling with setups times
- Eulerian graphs and related topics. Part 1, Volume 2
- Expected Computation Time for Hamiltonian Path problem
- Generalized polymatroids and submodular flows
- Heuristic analysis, linear programming and branch and bound
- scientific article; zbMATH DE number 437525 (Why is no real title available?)
- scientific article; zbMATH DE number 3906513 (Why is no real title available?)
- scientific article; zbMATH DE number 3746840 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3393943 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- Improving Christofides' algorithm for the s-t path TSP
- Many-visits TSP revisited
- Maximum Scatter TSP in Doubling Metrics
- Minimizing total completion time subject to release dates and sequence-dependent processing times
- Minimum cost flow with set-constraints
- On the high multiplicity traveling salesman problem
- Primal-dual meets local search: approximating MST's with nonuniform degree bounds
- Reassembling trees for the traveling salesman
- Reducing path TSP to TSP
- Scheduling aircraft landings -- the static case
- Sequencing jobs that require common resources on a single machine: A solvable case of the TSP
- Submodular function minimization
- The salesman's improved paths through forests
- The Traveling Salesman Problem with Many Visits to Few Cities
- Time- and space-optimal algorithm for the many-visits TSP
- What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
- Worst-case analysis of a new heuristic for the travelling salesman problem
Cited in
(9)- Many-visits TSP revisited
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
- Time- and space-optimal algorithm for the many-visits TSP
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- A time- and space-optimal algorithm for the many-visits TSP
- A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
- A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
This page was built for publication: A 3/2-Approximation for the Metric Many-Visits Path TSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5055644)
