Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Time

Abstract

We give a nearly linear time randomized approximation scheme for the Held-Karp bound [Held and Karp, 1970] for metric TSP. Formally, given an undirected edge-weighted graph $G$ on $m$ edges and $\epsilon >0$, the algorithm outputs in $O(m{\log }^{4}n/{\epsilon }^2)$ time, with high probability, a $(1+\epsilon )$-approximation to the Held-Karp bound on the metric TSP instance induced by the shortest path metric on $G$. The algorithm can also be used to output a corresponding solution to the Subtour Elimination LP. We substantially improve upon the $O(m^2{\log }^2(m)/{\epsilon }^2)$ running time achieved previously by Garg and Khandekar. The LP solution can be used to obtain a fast randomized $(\frac{3}{2}+\epsilon )$-approximation for metric TSP which improves upon the running time of previous implementations of Christofides' algorithm.