Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane

Richard M. Karp

doi:10.1287/moor.2.3.209

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

Travelling salesman problemMathematicsHeuristicProbabilistic logicSet (abstract data type)Plane (geometry)Mathematical optimizationAlgorithmBottleneck traveling salesman problemProbabilistic analysis of algorithmsTraveling purchaser problemGroup (periodic table)CombinatoricsComputer scienceStatistics

Affiliated Institutions

University of California, Berkeley US

Related Publications

An Effective Heuristic Algorithm for the Traveling-Salesman Problem

Simon 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. The procedure is base...

1973 Operations Research 3741 citations

Local Search for the Asymmetric Traveling Salesman Problem

Paris-C. Kanellakis , Christos H. Papadimitriou

We present an extension of the Lin-Kernighan local search algorithm for the solution of the asymmetric traveling salesman problem. Computational results suggest that our heurist...

1980 Operations Research 108 citations

Computer Solutions of the Traveling Salesman Problem

Shen Lin

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...

1965 Bell System Technical Journal 1957 citations

An Analysis of Several Heuristics for the Traveling Salesman Problem

Daniel J. Rosenkrantz , Richard E. Stearns , Philip Lewis

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 th...

1977 SIAM Journal on Computing 781 citations

An Algorithm for the Traveling Salesman Problem

John D. C. Little , Katta G. Murty , Dura W. Sweeney +1 more

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...

1963 Operations Research 1037 citations

Publication Info

Year: 1977
Type: article
Volume: 2
Issue: 3
Pages: 209-224
Citations: 441
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

441

OpenAlex

Cite This

APA Style

                            
                                    Richard M. Karp
                                
                            (1977). 
                            Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane. 
                            Mathematics of Operations Research
                            , 2
                            (3)
                            , 209-224.
                            https://doi.org/10.1287/moor.2.3.209

Identifiers

DOI: 10.1287/moor.2.3.209