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

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