A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem
Michel X. Goemans, Nicholas J. A. Harvey, Kamal Kishore Jain, Mohit Singh · arXiv (Cornell University) · 2009
We present an algorithm for the asymmetric traveling salesman problem on instances which satisfy the triangle inequality. Like several existing algorithms, it achieves approximation ratio O(log n). Unlike previous algorithms, it uses randomized rounding.