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

Chandra Chekuri, Kent Quanrud

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…