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 \times V \mapsto \mathbb{R}_{\geq 0}$ satisfying the triangle inequality, the \emph{metricity degree} of $G$ is defined as $\beta=\max_{x,y,z \in V} \big\{ \frac{c(x,y)}{c(x,z)+c(y,z)}\big\} \in \big[\frac{1}{2},1\big]$. This value is instrumental to establish the approximability of several $\np$-hard optimization problems definable on $G$, like for instance the prominent \emph{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 $\frac{2-\beta}{3(1-\beta)}$ or $\frac{3\beta^2}{3 \beta^2-2\beta+1}$, for $\beta < \frac{2}{3}$ or $\beta \geq \frac{2}{3}$, respectively. Nevertheless, these approximation algorithms have $O(n^3)$ and $O(n^{2.5} \log ^{1.5} n)$ running time, respectively, and therefore they are superlinear in the $\Theta(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 linear time are sought. With this restriction, the currently most efficient available solution is given by the classic $\mathtt{Double}\mbox{-}\mathtt{MST \ shortcut}$ algorithm, which in $O(n^2)$ time returns a solution within a factor $\frac{2\beta^2}{2\beta^2-2\beta+1}$ from the optimum. In this paper, we develop an enhanced but still linear-time version of this latter algorithm, which returns a $2\beta$-approximate solution, and thus always outperforms its counterpart. Indeed, we show that for any $1/2 < \beta < 1$, the performance ratio of the double-tree shortcutting algorithm is strictly larger than $2 \beta$. Furthermore, as a by-product of our result, it turns out that one of the most efficient heuristic for the metric TSP, namely the $\mathtt{Double}\mbox{-}\mathtt{MST\ Min}\mbox{-}\mathtt{weight\ shortcut}$ algorithm proposed by Deineko and Tiskin, has actually performance ratio not larger than $2\beta$. Previously, only the straightforward performance guarantee of 2 was known for this heuristic. Computational experiments suggest that our algorithm computes solutions of comparable quality to those produced by the Christofides algorithm, while requiring a significantly smaller running time.