Fast Approximations for Metric-TSP via Linear Programming
share
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 O(n n /ϵ^2) edges. The running time of the algorithm is Õ(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 + ϵ) 3/2 times the minimum cost tour of G in time Õ(m/ϵ^2 + n^1.5/ϵ^3). Previous implementations of Christofides' algorithm [Christofides, 1976] require, for a 3/2-optimal tour, Õ(n^2.5) time when the metric is explicitly given, or Õ({m^1.5, mn+n^2.5}) time when the metric is given implicitly as the shortest path metric of a weighted graph.
READ FULL TEXT