An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Authors:
- 1 August 2017
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 65 (4) , 1043-1061
Abstract
We present a randomized O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem (ATSP). This provides the first asymptotic improvement over the long-standing Θ(log n)-approximation bound stemming from the work of Frieze et al. (1982) [Frieze AM, Galbiati G, Maffioki F (1982) On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12(1):23–39]. The key ingredient of our approach is a new connection between the approximability of the ATSP and the notion of so-called thin trees. To exploit this connection, we employ maximum entropy rounding—a novel method of randomized rounding of LP relaxations of optimization problems. We believe that this method might be of independent interest.Keywords
This publication has 33 references indexed in Scilit:
- The weak 3-flow conjecture and the weak circular flow conjectureJournal of Combinatorial Theory, Series B, 2012
- An Approximation Algorithm for Max-Min Fair Allocation of Indivisible GoodsSIAM Journal on Computing, 2010
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphsJournal of the ACM, 2005
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entriesJournal of the ACM, 2004
- Two Algorithms for Unranking ArborescencesJournal of Algorithms, 1996
- Generating random combinatorial objectsJournal of Algorithms, 1990
- Random spanning treeJournal of Algorithms, 1983
- On the worst‐case performance of some algorithms for the asymmetric traveling salesman problemNetworks, 1982
- Some Simple Applications of the Travelling Salesman ProblemJournal of the Operational Research Society, 1975
- Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wirdAnnalen der Physik, 1847