Given $n$ nodes uniformly distributed in $[0,1]^2$, consider the nearest neighbor algorithm to solve traveling salesman problem, i.e., each time I select the nearest neighbor not visited so far as the next node to visit, my question is: what is the expected length of such TSP tour?


1 Answer 1


A careful experimental analysis of the nearest-neighbor (NN) heuristic (among other heuristics) is described 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 find that the growth rate, in comparison to the Karp-Held lower bound, "appears to be proportional to $\log n$" for "random distance matrices." This is the theoretical growth rate w.r.t. the optimum. In contrast, for "random Euclidean instances" up to $n=10^6$, they find (Table 1, p.15) that the NN heuristic leads to paths nearly constantly about 25% longer than the Karp-Held lower bound. This is closer (but not identical) to the OP's "uniformly distributed within $[0,1]^2$." The section, "Standard Test Instances" on pp.12-14 unpacks "random Euclidean instances."

Incidentally, the observed running time grows subquadratically.

(See also the follow-up MO question, "Travelling Salesman Problem: Can the nearest neighbor algorithm be n times longer than the optimal solution?.")


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.