On the nearest neighbor rule for the traveling salesman problem


Hurkens, Cor A.J. and Woeginger, Gerhard J. (2004) On the nearest neighbor rule for the traveling salesman problem. Operations Research Letters, 32 (1). pp. 1-4. ISSN 0167-6377

[img] PDF
Restricted to UT campus only
: Request a copy
Abstract:Rosenkrantz et al. (SIAM J. Comput. 6 (1977) 563) and Johnson and Papadimitriou (in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985, pp. 145–180, (Chapter 5)) constructed families of TSP instances with n cities for which the nearest neighbor rule yields a tour-length that is a factor Ω(log n) above the length of the optimal tour.

We describe two new families of TSP instances, for which the nearest neighbor rule shows the same bad behavior. The instances in the first family are graphical, and the instances in the second family are Euclidean. Our construction and our arguments are extremely simple and suitable for classroom use.
Item Type:Article
Copyright:© 2004 Elsevier
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/76272
Official URL:https://doi.org/10.1016/S0167-6377(03)00093-2
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 219736