RATES OF CONVERGENCE OF MEANS FOR DISTANCE-MINIMIZING SUBADDITIVE EUCLIDEAN FUNCTIONALS
成果类型：
Article
署名作者：
Alexander, Kenneth S.
署名单位：
University of Southern California
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/aoap/1177004976
发表日期：
1994
页码：
902-922
关键词：
摘要：
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.
来源URL：