Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
Mathematics of Operations ResearchPublished 1 August 1977
Richard M. Karp
Citations443
SJR quartileQ1
SJR score1.35
SNIP1.90
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work considers partitioning algorithms for the approximate solution of large instances of the traveling-salesman problem in the plane, in which partitioning is used in conjunction with existing heuristic algorithms.
Abstract
We consider partitioning algorithms for the approximate solution of large instances of the traveling-salesman problem in the plane. These algorithms subdivide the set of cities into small groups, construct an optimum tour through each group, and then patch the subtours together to form a tour through all the cities. If the number of cities in the problem is n, and the number of cities in each group is t, then the worst-case error is [Formula: see text]. If the cities are randomly distributed, then the relative error is O(t −1/2 ) (with probability one). Hybrid schemes are suggested, in which partitioning is used in conjunction with existing heuristic algorithms. These hybrid schemes may be expected to give near-optimum solutions to problems with thousands of cities.
Keywords
Computer ScienceEngineering
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
Operations ResearchThe Traveling-Salesman Problem and Minimum Spanning Trees
1,443 Citations1970Michael Held, Richard M. Karp
It is shown that maxπwπ = C* precisely when a certain well-known linear program has an optimal solution in integers.
Journal of the Society for Industrial and Applied MathematicsA Dynamic Programming Approach to Sequencing Problems
1,253 Citations1962Michael Held, Richard M. Karp
Operations Research ForumWorst-Case Analysis of a New Heuristic for the Travelling Salesman Problem
1,142 Citations2022Nicos Christofides
An O(n3) heuristic algorithm is described for solving d-city travelling salesman problems (TSP) whose cost matrix satisfies the triangularity condition and a worst-case analysis of this heuristic shows that the ratio of the answer obtained to the optimum TSP solution is strictly less than 3/2.
Closest-point problems
1,062 Citations1975Michael Ian Shamos, Dan Hoey
The purpose of this paper is to introduce a single geometric structure, called the Voronoi diagram, which can be constructed rapidly and contains all of the relevant proximity information in only linear space, and is used to obtain O(N log N) algorithms for most of the problems considered.
Mathematical ProgrammingThe traveling-salesman problem and minimum spanning trees: Part II
1,017 Citations1971Michael Held, Richard M. Karp
An efficient iterative method for approximating this bound closely from below is presented, and a branch-and-bound procedure based upon these considerations has easily produced proven optimum solutions to all traveling-salesman problems presented to it.
Mathematical Proceedings of the Cambridge Philosophical SocietyThe shortest path through many points
955 Citations1959Jillian Beardwood, John H. Halton +1 more
Journal of the ACMDynamic Programming Treatment of the Travelling Salesman Problem
783 Citations1962Richard Bellman
This problem can be formulated in dynamic programming terms, and resolved computationally for up to 17 cities, and combined with various simple manipulations may be used to obtain quick approximate solutions.
Theoretical Computer ScienceThe Euclidean travelling salesman problem is NP-complete
775 Citations1977Christos H. Papadimitriou
Some NP-complete geometric problems
394 Citations1976M. R. Garey, Ron Graham +1 more
It is shown that the STEINER TREE problem and TRAVELING SALESman problem for points in the plane are NP-complete when distances are measured either by the rectilinear (Manhattan) metric or by a natural discretized version of the Euclidean metric.
Geometric complexity
264 Citations1975Michael Ian Shamos
An effort is made to recast classical theorems into a useful computational form and analogies are developed between constructibility questions in Euclidean geometry and computability questions in modern computational complexity.
Communications of the ACMA man-machine approach toward solving the traveling salesman problem
139 Citations1971Patrick D. Krolak, Wayne Felts +1 more
A computer-aided heuristic technique which uses only a modest amount of computer time in real time to solve large point problems and can be taught to inexperienced persons and their results are similar to those of the authors'
Approximate algorithms for the traveling salesperson problem
125 Citations1974Daniel J. Rosenkrantz, Richard E. Stearns +1 more
Several polynomial time algorithms finding "good," but not necessarily optimal, tours for the traveling salesman problem are considered, and the worst case ratio of the obtained tour to the optimal tour is shown to increase logarithmically with the number of cities.
Mathematical ProgrammingImprovements of the Held—Karp algorithm for the symmetric traveling-salesman problem
78 Citations1974Keld Helbig Hansen, Jakob Krarup
A highly efficient algorithm (HK) devised by Held and Karp for solving the symmetric traveling-salesman problem was presented at the 7th Mathematical programming Symposium in 1970 and published in Mathematical Programming in 1971.