Approximating the Metric TSP in Linear Time

Given a metric graph G=(V,E) of n vertices, i.e., a complete graph with a non-negative real edge cost function satisfying the triangle inequality, the metricity degree of G is defined as β=maxx,y,z∈V{c(x,y)c(x,z)+c(y,z)}∈[12,1] . This value is instrumental to establish the approximability of several NP-hard optimization problems definable on G, like for instance the prominent traveling salesman problem, which asks for finding a Hamiltonian cycle of G of minimum total cost. In fact, this problem can be approximated quite accurately depending on the metricity degree of G, namely by a ratio of either 2−β3(1−β) or 3β23β2−2β+1 , for β<23 or β≥23 , respectively. Nevertheless, these approximation algorithms have O(n 3) and O(n 2.5log 1.5 n) running time, respectively, and therefore they are superlinear in the Θ(n 2) input size. Thus, since many real-world problems are modeled by graphs of huge size, their use might turn out to be unfeasible in practice, and alternative approaches requiring only O(n 2) time are sought. However, with this restriction, all the currently available approaches can only guarantee a 2-approximation ratio for the case β=1, which means a 2β22β2−2β+1 -approximation ratio for general β<1. In this paper, we show how to elaborate—without affecting the space and time complexity—one of these approaches, namely the classic double-MST heuristic, in order to obtain a 2β-approximate solution. This improvement is effective, since we show that the double-MST heuristic has in general a performance ratio strictly larger than 2β, and we further show that any alternative elaboration of it cannot lead to a performance ratio better than 2β−ε, for any ε>0. Our theoretical results are complemented with an extensive series of experiments, that show the practical appeal of our approach.