WORST CASE LENGTH OF NEAREST NEIGHBOR TOURS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM.

The worst case length of a tour for the Euclidean traveling salesman problem produced by the nearest neighbor (NN) heuristic is studied in this paper. Nearest neighbor tours for a set of arbitrarily located points in the d-dimensional unit cube are considered. A technique is developed for bounding the worst case length of a tour. It is based on identifying sequences of coverings of [0,1]d. Each covering Pk consists of sets Ci, with diameter bounded by the diameter D(Pk) of the covering. For every sequence of coverings a bound is obtained that depends on the cardinality of the coverings and their diameters. The task of bounding the worst case length of an NN tour is reduced to finding appropriate sequences of coverings. Using coverings produced by the rectangular lattice with appropriately shrinking diameter, it is shown that the worst case length of an NN tour through Ar points in [0,1]d is bounded by [d√d/(d-1)]N(d-1)/d + o(N(d-1)/d). For the unit square the tighter bound 2.482→N + o(√N) is obtained using regular hexagonal lattice coverings. [ABSTRACT FROM AUTHOR]