RATES OF CONVERGENCE OF MEANS FOR DISTANCE-MINIMIZING SUBADDITIVE EUCLIDEAN FUNCTIONALS

Functionals L on finite subsets A of R'1 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 {X1,, X,,} a uniform i.i.d. sample from [0,1](d), EL({X-1, . . . , 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.