A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- 3 November 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 67 (6), 1-53
- https://doi.org/10.1145/3424306
Abstract
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. The main idea of our approach is a reduction to Subtour Partition Cover, an easier problem obtained by significantly relaxing the general connectivity requirements into local connectivity conditions. We first show that any algorithm for Subtour Partition Cover can be turned into an algorithm for ATSP while only losing a small constant factor in the performance guarantee. Next, we present a reduction from general ATSP instances to structured instances, on which we then solve Subtour Partition Cover, yielding our constant-factor approximation algorithm for ATSP.Keywords
Funding Information
- European Research Council (335288?OptApprox,757481?ScaleOpt)
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (200021-184656)
- Engineering and Physical Sciences Research Council (EP/M02797X/1)
This publication has 25 references indexed in Scilit:
- New Inapproximability Bounds for TSPLecture Notes in Computer Science, 2013
- The Asymmetric Traveling Salesman Problem on Graphs with Bounded GenusPublished by Society for Industrial & Applied Mathematics (SIAM) ,2011
- A new approximation algorithm for the asymmetric TSP with triangle inequalityACM Transactions on Algorithms, 2008
- On the Integrality Ratio for the Asymmetric Traveling Salesman ProblemMathematics of Operations Research, 2006
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphsJournal of the ACM, 2005
- How to tidy up a symmetric set-system by use of uncrossing operationsTheoretical Computer Science, 1996
- The traveling salesman problem on a graph and some related integer polyhedraMathematical Programming, 1985
- Guaranteed performance heuristics for the bottleneck travelling salesman problemOperations Research Letters, 1984
- On the worst‐case performance of some algorithms for the asymmetric traveling salesman problemNetworks, 1982
- Finding EPS-graphsMonatshefte für Mathematik, 1981