  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^4n /\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
$\big(\frac{3}{2} + \epsilon\big)$-approximation for metric TSP which improves
upon the running time of previous implementations of Christofides' algorithm.

Data Structures and Algorithms