# Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the optimal solution?

This is inspired by a recent question.

Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the nearest-neighbor algorithm (described below) gives a tour that is $n$ times longer than the optimal solution starting at $s$?

Starting at $s$, pick the nearest neighbor not visited so far as the next node to visit.

EDIT: If the answer is no, what is the maximum value that the ratio $r$ of "nearest neighbor trip" vs "best trip" can take?

• Does not exist. It all depends on the position of the points. You can even choose the location that this algorithm is optimal. Jun 26, 2015 at 6:46
• So what is the biggest factor nearest neighbor trip vs best trip can take? Jun 26, 2015 at 6:48
• Should the task of paraphrase. Takes a random number of points $n$ they randomly have on the plane. And with some random points start to crawl by this algorithm outperforming all points. And need to know the mathematical expectation of how many times it is not effective? The number of points does not play any role. Jun 26, 2015 at 7:01
• See the answer to this question: cstheory.stackexchange.com/questions/18307/… Jun 26, 2015 at 10:03
• Thanks - can you make this into an answer, please? Jun 26, 2015 at 11:31

The nearest-neighbor (NN) heuristic (among others) is analyzed in this paper:

Johnson, David S., and Lyle A. McGeoch. "The traveling salesman problem: A case study in local optimization." Local search in combinatorial optimization 1 (1997): 215-310. (PDF download link.)

They say:

In the specific case of "random Euclidean instances" (in contrast to "random distance matrices"), they observe experimentally a fixed ~25% longer path length, which would exceed any fixed $n$ for large enough nodes $N$. In terms of both theory and experiments with random distance matrices, the growth rate is $\log N$. Either way, any fixed $n$ could be exceeded with sufficiently large $N$, so the answer to the OP's question is Yes.

The cited paper is: Rosenkrantz, Daniel J., Richard E. Stearns, and Philip M. Lewis, II. "An analysis of several heuristics for the traveling salesman problem." SIAM Journal on Computing 6.3 (1977): 563-581. (Journal link.)

Added (in response to question from Manfred). Here is the essence of the Rosenkrantz et al. lower bound:

(Slide from David Johnson PowerPoint Lecture.)

• Doesn't that mean that the answer to the first question is Yes? Given $n$, we can always choose $N$ so that $0.5(\lceil \log_2N\rceil+1) > n$. Jun 26, 2015 at 13:44
• @TonyK: Oh, you are right, I was mixing $n$ with $N$. :-) Jun 26, 2015 at 13:59
• Doesn't the paper refer to the metric TSP, whereas the OP is asking about the special case of TSP in the plane? Jun 26, 2015 at 14:27
• @BillBradley: Good point. In the Johnson-McGeoch experimental results (p.15), they distinguish between "random Euclidean instances" and "random distance matrices." The former approach a fixed 25% longer than the K-H lower bound. I will correct my answer. Jun 26, 2015 at 14:36
• You're still saying No... Jun 26, 2015 at 14:52