An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem

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, Maffi...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 2017-07, Vol.65 (4), p.1043-1061
Main Authors: Asadpour, Arash, Goemans, Michel X., Mądry, Aleksander, Gharan, Shayan Oveis, Saberi, Amin
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Asymmetry
Asymptotic methods
Evaluation
Held-Karp relaxation
linear programming
Management science
Mathematical analysis
Mathematical problems
Maximum entropy
METHODS
Operations research
Optimization
randomized rounding
Rounding
thin tree
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.2017.1603