On the nearest neighbor rule for the Traveling Salesman Problem

Cor A.J. Hurkens, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

44 Citations (Scopus)
73 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)1-4
Number of pages4
JournalOperations research letters
Issue number1
Publication statusPublished - 2004


  • Heuristic
  • Lower bound
  • Traveling Salesman Problem


Dive into the research topics of 'On the nearest neighbor rule for the Traveling Salesman Problem'. Together they form a unique fingerprint.

Cite this