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 p roblem produced by the nearest neighbor (NN) heuristic is studied in t his paper. Nearest neighbor tours for a set of arbitrarily located poi nts in the d-dimensional unit cube are considered. A technique is deve loped for bounding the worst case length of a tour. It is based on ide ntifying sequences of coverings of [0, 1](d). Each covering P-k consis ts of sets C-i, with diameter bounded by the diameter D(P-k) of the co vering. For every sequence of coverings a bound is obtained that depen ds on the cardinality of the coverings and their diameters. The task o f bounding the worst case length of an NN tour is reduced to finding a ppropriate sequences of coverings. Using coverings produced by the rec tangular lattice with appropriately shrinking diameter, it is shown th at the worst case length of an NN tour through N points in [0, 1](d) i s bounded by [d root d/(d - 1)]N(d-1/d) + o(N(d-1/d)). For the unit sq uare the tighter bound 2.482 root N + o(root N)is obtained using regul ar hexagonal lattice coverings.