An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
From MaRDI portal
Publication:5863328
DOI10.1137/20M1339313OpenAlexW4213165341MaRDI QIDQ5863328
Publication date: 11 March 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1339313
Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (5)
Approximation algorithms for the min-max mixed rural postmen cover problem and its variants ⋮ Approximation algorithms for the min-max mixed rural postmen cover problem and its variants ⋮ 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 ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
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
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Better \(s-t\)-tours by Gao trees
- Constant factor approximation for ATSP with two edge weights
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- \(\frac{13}{9}\)-approximation for graphic TSP
- Reassembling Trees for the Traveling Salesman
- Improving Christofides' Algorithm for the s-t Path TSP
- Removing and Adding Edges for the Traveling Salesman Problem
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Eight-Fifth Approximation for the Path TSP
- Reducing path TSP to TSP
- An improved approximation algorithm for TSP in the half integral case
- The Salesman’s Improved Paths through Forests
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- A 1.5-Approximation for Path TSP
- Approaching 3/2 for the s - t -path TSP
- An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
- A Randomized Rounding Approach to the Traveling Salesman Problem
- The asymmetric traveling salesman path LP has constant integrality ratio
This page was built for publication: An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
