Complete Convergence of Short Paths and Karp's Algorithm for the TSP

Abstract

Let X i , 1 ≤ i < ∞, be uniformly distributed in [0, 1] 2 and let T n be the length of the shortest closed path connecting {X 1 , X 2 , …, X n }. It is proved that there is a constant 0 < β < ∞ such that for all ϵ > 0 [Formula: see text] This result is essential in justifying Karp's algorithm for the traveling salesman problem under the independent model, and it settles a question posed by B. W. Weide.

Locations

• ScholarlyCommons (University of Pennsylvania) - View - PDF
• Mathematics of Operations Research - View