Xref: utzoo comp.theory:1632 sci.math:15646
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!pitt!speedy.cs.pitt.edu!kirk
From: kirk@speedy.cs.pitt.edu (Kirk Pruhs)
Newsgroups: comp.theory,sci.math
Subject: Nearest Neighbor for TSP
Message-ID: <10090@pitt.UUCP>
Date: 9 Mar 91 22:13:55 GMT
Sender: news@pitt.UUCP
Reply-To: kirk@cs.pitt.edu.UUCP (Kirk Pruhs)
Organization: Univ. of Pittsburgh Computer Science
Lines: 15


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