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

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:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 219736