AnO(logn/log logn)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, Amin Saberi
Operations Research · 2017 · Volume 65 · Issue 4
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
traveling salesman problem, linear programming, maximum entropy, thin tree, Held-Karp relaxation, randomized rounding
Enable JavaScript for citation tools and additional paper interactions.