An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
From MaRDI portal
Publication:5863328
Recommendations
- An improved approximation algorithm for ATSP
- A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
Cites work
- scientific article; zbMATH DE number 3746840 (Why is no real title available?)
- scientific article; zbMATH DE number 2079394 (Why is no real title available?)
- A 1.5-approximation for path TSP
- A Randomized Rounding Approach to the Traveling Salesman Problem
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
- An improved approximation algorithm for TSP in the half integral case
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Approaching 3/2 for the \(s\)-\(t\)-path TSP
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- Better \(s-t\)-tours by Gao trees
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Constant factor approximation for ATSP with two edge weights
- Eight-fifth approximation for the path TSP
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
- New inapproximability bounds for TSP
- On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Reassembling trees for the traveling salesman
- Reducing path TSP to TSP
- 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 salesman's improved paths through forests
- \(\frac{13}{9}\)-approximation for graphic TSP
Cited in
(21)- Algorithms and Data Structures
- scientific article; zbMATH DE number 6178353 (Why is no real title available?)
- Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
- A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem
- Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
- scientific article; zbMATH DE number 5899262 (Why is no real title available?)
- scientific article; zbMATH DE number 2079394 (Why is no real title available?)
- Evaluation of The Contract Or-Patch Heuristic Eor The Asymmetric Tsp1
- Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
- Technical Note—An Improved Transformation of the Symmetric Multiple Traveling Salesman Problem
- The on-line asymmetric traveling salesman problem
- Approximations for the Steiner multicycle problem
- scientific article; zbMATH DE number 1893558 (Why is no real title available?)
- The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
- A new approximation algorithm for the asymmetric TSP with triangle inequality
- Approximation algorithms with constant factors for a series of asymmetric routing problems
- Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles
- New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
- Improved first player strategy for the zero-sum sequential uncrossing game
- Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem
- An effective hybrid harmony search for the asymmetric travelling salesman problem
This page was built for publication: An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5863328)
