An <i>O</i>(log <i>n</i>/log log <i>n</i>)-approximation Algorithm for the Asymmetric Traveling Salesman Problem

Abstract

We consider the Asymmetric Traveling Salesman problem for costs satisfying the triangle inequality. We derive a randomized algorithm which delivers a solution within a factor O(log n/ log log n) of the optimum with high probability.