2017/02/14 by Chekuri, Chandra, Quanrud, Kent
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1702.04307
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 ε> 0, the algorithm outputs in O(m log4n /ε2) time, with high probability, a (1+ε)-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(m2 log2(m)/ε2) running time achieved previously by Garg and Khandekar. The LP solution can be used to obtain a fast randomized ((3)/(2) + ε)-approximation for metric TSP which improves upon the running time of previous implementations of Christofides' algorithm.