2018/02/05 by Chekuri, Chandra, Quanrud, Kent
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1802.01242
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 log 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 + n1.5/ε3). Previous implementations of Christofides' algorithm [Christofides, 1976] require, for a (3)/(2)-optimal tour, Õ(n2.5) time when the metric is explicitly given, or Õ(min\m1.5, mn+n2.5\) time when the metric is given implicitly as the shortest path metric of a weighted graph.