## Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem.(English)Zbl 0733.90072

Summary: 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 $\beta_{HK}(d)n^{(d-1)/d}\int f(x)^{(d-1)/d}dx,$ where $$\beta_{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 $\beta_{TSP}(d)n^{(d-1)/d}\int 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.

### MSC:

 90C35 Programming involving graphs or networks 90C27 Combinatorial optimization 90C60 Abstract computational complexity for mathematical programming problems 90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: