Back to Search
Start Over
AN IMPROVED APPROXIMATION ALGORITHM FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM.
- Source :
-
SIAM Journal on Computing . 2022, Vol. 51 Issue 1, p139-173. 35p. - Publication Year :
- 2022
-
Abstract
- We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and V\'egh [J. ACM, 67 (2020), 37]. We improve on each part of this algorithm. We avoid the reduction to irreducible instances and thus obtain a simpler and much better reduction to vertebrate pairs. We also show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from 506 to 22 + ε for any ε > 0. This also improves the upper bound on the integrality ratio from 319 to 22. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*TRAVELING salesman problem
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 51
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 155447947
- Full Text :
- https://doi.org/10.1137/20M1339313