Approximation Results Toward Nearest Neighbor Heuristic


Jérôme Monnot




In this paper, we revisit the famous heuristic called nearest neighbor ($NN$ ) for the traveling salesman problem under maximization and minimization goal. We deal with variants where the edge costs belong to interval $[a;ta]$ for $a > 0$ and $t > 1$, which certainly corresponds to practical cases of these problems. We prove that $NN$ is a $(t+1)/2t$-approximation for max $TSP[a;ta]$ and $2/(t+1)$ -approximation for min $TSP[a;ta]$ under the standard performance ratio. Moreover, we show that these ratios are tight for some instances.