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)$.
Keywords
Travelling salesman problemUpper and lower boundsLogarithmMathematicsCombinatoricsConstant (computer programming)Christofides algorithmBounded functionCompetitive analysisHeuristicsBottleneck traveling salesman problemEnhanced Data Rates for GSM EvolutionDiscrete mathematicsMathematical optimizationComputer science
Affiliated Institutions
Related Publications
An Algorithm for the Traveling Salesman Problem
A “branch and bound” algorithm is presented for solving the traveling salesman problem. The set of all tours (feasible solutions) is broken up into increasingly small subsets by...
Fast Algorithms for Geometric Traveling Salesman Problems
This paper describes efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets. We describe implementations of a dozen starting heur...
MAX-MIN Ant System and local search for the traveling salesman problem
Ant System is a general purpose algorithm inspired by the study of the behavior of ant colonies. It is based on a cooperative search paradigm that is applicable to the solution ...
An Effective Heuristic Algorithm for the Traveling-Salesman Problem
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem. The procedure is base...
Computer Solutions of the Traveling Salesman Problem
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer. The first produces guaranteed optimal solu...
Publication Info
- Year
- 1977
- Type
- article
- Volume
- 6
- Issue
- 3
- Pages
- 563-581
- Citations
- 781
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
781
OpenAlex
Cite This
Daniel J. Rosenkrantz,
Richard E. Stearns,
Philip Lewis
(1977).
An Analysis of Several Heuristics for the Traveling Salesman Problem.
SIAM Journal on Computing
, 6
(3)
, 563-581.
https://doi.org/10.1137/0206041
Identifiers
- DOI
- 10.1137/0206041