Approximating the Metric TSP in Linear Time

Given a metric graph G = (V,E) of n vertices, i.e., a complete graph with an edge cost function c:V ×V →ℝ ≥ 0 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.5 log1.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 the 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 enhance –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 that 2 β, and we further show that any re-elaboration of the shortcutting phase therein provided, cannot lead to a performance ratio better than 2β.