On the nearest neighbor rule for the traveling salesman problem

On the nearest neighbor rule for the traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20043362
Country: Netherlands
Volume: 32
Issue: 1
Start Page Number: 1
End Page Number: 4
Publication Date: Jan 2004
Journal: Operations Research Letters
Authors: ,
Abstract:

Rosenkrantz et al. and Johnson and Papadimitriou 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 behaviour. 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.

Reviews

Required fields are marked *. Your email address will not be published.