On the nearest neighbor rule for the traveling salesman problem

Share/Save/Bookmark

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
214Kb
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
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/76272
Official URL:http://dx.doi.org/10.1016/S0167-6377(03)00093-2
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 219736