An Analysis of Several Heuristics for the Traveling Salesman Problem

Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis IiSIAM Journal on Computing 1977 · OpenReview

Abstract

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\geqq 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)$.
BibTeX
@article{rosenkrantz1977analysis,
  author = {Daniel J. Rosenkrantz and Richard Edwin Stearns and Philip M. Lewis II},
  title = {{An Analysis of Several Heuristics for the Traveling Salesman Problem}},
  journal = {SIAM Journal on Computing},
  year = {1977},
  url = {https://openreview.net/forum?id=_KzAYc8Ya7U},
}

Loading related content...

Figure