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

• 成果类型: Article
• 署名作者: Asadpour, Arash; Goemans, Michel X.; Madry, Aleksander; Gharan, Shayan Oveis; Saberi, Amin
• 署名单位: New York University; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University of Washington; University of Washington Seattle; Stanford University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1603
• 发表日期: 2017
• 页码: 1043-1061
• 关键词: APPROXIMATION ALGORITHM

摘要

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 Theta(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.