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

Abstract

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. © Applied Probability Trust 2014.