An Analysis of Several Heuristics for the Traveling Salesman Problem

Several polynomial time algorithms finding “good, ” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to the minimal tour length. For the nearest neighbor method, we show the ratio is bounded above by a logarithmic function of the number of nodes. We also provide a logarithmic lower bound on the worst case. A class of approximation methods we call insertion methods are studied, and these are also shown to have a logarithmic upper bound. For two specific insertion methods, which we call nearest insertion and cheapest insertion, the ratio is shown to have a constant upper bound of 2, and examples are provided that come arbitrarily close to this upper bound. It is also shown that for any n 8, there are traveling salesman problems with n nodes having tours which cannot be improved by making n/4 edge changes, but for which the ratio is 2 (1-1/n).