On the nearest-neighbor algorithm for the mean-field traveling salesman problem

• Autores: Antar Bandyopadhyay, Farkhondeh Sajadi
• Localización: Journal of Applied Probability, ISSN-e 0021-9002, Vol. 51, Nº. 1, 2014, págs. 106-117
• Idioma: inglés
• DOI: 10.1017/s0001867800010119
• Texto completo no disponible (Saber más ...)
• Resumen

  • In this work we consider the mean-field traveling salesman problem, where the intercity distances are taken to be independent and identically distributed with some distribution F. We consider the simplest approximation algorithm, namely, the nearest-neighbor algorithm, where the rule is to move to the nearest nonvisited city. We show that the limiting behavior of the total length of the nearest-neighbor tour depends on the scaling properties of the density of F at 0 and derive the limits for all possible cases of general F.