Fast Approximations for Metric-TSP via Linear Programming

We develop faster approximation algorithms for Metric-TSP building on recent, nearly linear time approximation schemes for the LP relaxation [Chekuri and Quanrud, 2017]. We show that the LP solution can be sparsified via cut-sparsification techniques such as those of Benczur and Karger [2015]. Given a weighted graph $G$ with $m$ edges and $n$ vertices, and $ε> 0$, our randomized algorithm outputs with high probability a $(1+ε)$-approximate solution to the LP relaxation whose support has $\operatorname{O}(n \log n /ε^2)$ edges. The running time of the algorithm is $\operatorname{Õ}(m/ε^2)$. This can be generically used to speed up algorithms that rely on the LP. For Metric-TSP, we obtain the following concrete result. For a weighted graph $G$ with $m$ edges and $n$ vertices, and $ε> 0$, we describe an algorithm that outputs with high probability a tour of $G$ with cost at most $(1 + ε) \frac{3}{2}$ times the minimum cost tour of $G$ in time $\operatorname{Õ}(m/ε^2 + n^{1.5}/ε^3)$. Previous implementations of Christofides' algorithm [Christofides, 1976] require, for a $\frac{3}{2}$-optimal tour, $\operatorname{Õ}(n^{2.5})$ time when the metric is explicitly given, or $\operatorname{Õ}(\min\{m^{1.5}, mn+n^{2.5}\})$ time when the metric is given implicitly as the shortest path metric of a weighted graph.