Asymptotics for Euclidean functionals with power-weighted edges

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:61

Article

Redmond, C ; Yukich, JE

关键词: combinatorial optimization;    boundary processes;    minimal spanning tree;    traveling salesman problem;    minimal matching;    Euclidean functional;    rates of convergence;   

DOI  :  10.1016/0304-4149(95)00075-5

来源: Elsevier

【 摘 要 】

We provide general and relatively simple conditions under which Euclidean functionals L(p) on [0, 1](d) with pth power-weighted edges satisfy the limit [GRAPHICS] where X(i), i greater than or equal to 1, are i.i.d. random variables with values in [0, 1](d), 0 < p < d, beta := beta(LP, d) is a constant, f is the density of the absolutely continuous part of the law of X(1), and c.c denotes complete convergence. This general result is shown to apply to the minimal spanning tree, shortest tour, and minimal matching functionals. The approach provides a rate of convergence for the power-weighted minimal spanning tree functional, resolving a question raised by Steele (1988).

【 授权许可】

Free