← Search

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

Arash Asadpour¹; Michel X. Goemans²; Aleksander Mądry³; Shayan Oveis Gharan⁴; Amin Saberi⁵

¹ Department of Information, Operations, and Management Science, New York University Stern School of Business, New York, New York 10012 · ² Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139 · ³ Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139; · ⁴ Department of Computer Science and Engineering, University of Washington, Seattle, Washington 98105 · ⁵ Department of Management Science and Engineering, Stanford University, Stanford, California 94305

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.

DOI

10.1287/opre.2017.1603

Volume

65 (4)

Pages

1043-1061

Language

en

Export

BibTeX

Sources

crossref