Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem

We analyze probabilistically the classical Held-Karp lower bound derived from the 1-tree relaxation for the Euclidean traveling salesman problem (ETSP). We prove that, if n points are identically and independently distributed according to a distribution with bounded support and absolutely continuous part f(x)dx over the d-cube, the Held-Karp lower bound on these n points is almost surely asymptotic to

β_HK(d)n^(d−1)/d ∫ f(x)^(d−1)/d dx,

where β_HK(d) is a constant independent of n. The result suggests a probabilistic explanation of the observation that the lower bound is very close to the length of the optimal tour in practice, since the ETSP is almost surely asymptotic to

β_TSP(d)n^(d−1)/d ∫ f(x)^(d−1)/d dx.

The techniques we use exploit the polyhedral description of the Held-Karp lower bound and the theory of subadditive Euclidean functionals.