Analysis of the Held-Karp lower bound for the asymmetric TSP

The paper shows that the Held-Karp lower bound for the asymmetric traveling salesman problem (ATSP) dominates the Balas-Christofides lower bound. For the ATSP with triangle inequality, it shows that it is also greater than , where is the cost of the optimal tour. In the course of proving these results, the paper provides alternate characterizations of the Held-Karp lower bound and proves that on instances which obey the triangle inequality, the lower bound is monotonic with respect to the set of nodes included.