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 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].