[sci.math] Nearest Neighbor for TSP

kirk@speedy.cs.pitt.edu (Kirk Pruhs) (03/10/91)

I am looking for a reference for the worst case performance of
the Nearest Neighbor Hueristic for the Traveling Salesman Problem
in the Euclidean Plane.  I have an article that claims that
Nearest Neighbor can produce a tour as bad as Omega((log n)/ log log n) 
times the optimal tour. However, the article justifies this claim 
by citing a nonexistent reference.
Any pointers to this result would be appreciated.

I already know that Nearest Neighbor produces a tour at 
most O(log n) times the optimal tour, and this is tight for an 
arbitrary metric space. 

Kirk Pruhs 
kirk@cs.pitt.edu