Alexander, Kenneth S. Rates of convergence of means for distance-minimizing subadditive Euclidean functionals. (English) Zbl 0809.60016 Ann. Appl. Probab. 4, No. 3, 902-922 (1994). Author’s summary: Functionals \(L\) on finite subsets \(A\) of \(\mathbb{R}^ d\) are considered for which the value is the minimum total edge length among a class of graphs with vertex set equal to, or in some cases containing, \(A\). Examples include minimal spanning trees, the traveling salesman problem, minimal matching and Steiner trees. Beardwood, Halton and Hammersley, and later Steele, have shown essentially that for \(\{X_ 1, \dots, X_ n\}\) a uniform i.i.d. sample from \([0,1]^ d\), \(EL(\{X_ 1, \dots, X_ n\})/n^{(d - 1)/d}\) converges to a finite constant. Here we bound the rate of this convergence, proving a conjecture of Beardwood, Halton and Hammersley. Reviewer: I.S.Molchanov (Amsterdam) Cited in 9 Documents MSC: 60D05 Geometric probability and stochastic geometry 05C80 Random graphs (graph-theoretic aspects) 90C27 Combinatorial optimization Keywords:subadditive Euclidean functional; traveling salesman problem; minimal spanning tree; Steiner tree; minimal matching × Cite Format Result Cite Review PDF Full Text: DOI