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

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

0.00 Avg rating0 Votes
Article ID: iaor20173091
Volume: 65
Issue: 4
Start Page Number: 1043
End Page Number: 1061
Publication Date: Aug 2017
Journal: Operations Research
Authors: , , , ,
Keywords: programming: travelling salesman, heuristics, programming: linear
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.

Reviews

Required fields are marked *. Your email address will not be published.