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.
There exists a result of O(log n/ log log n) for the randomized case REF .
An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem
SODA '10
Mathematics Computer Science