Asymptotic of power-weighted Euclidean functionals

DOI10.1016/S0304-4149(98)00065-9MaRDI QIDQ1593589zbMATH OpenOpenAlexFDO

Authors Sungchul Lee

Publication date 17 January 2001

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-4149(98)00065-9

zbMATH Keywords

minimal matchingminimal spanning treestrong law of large numberstravelling salesman problem

Mathematics Subject Classification ID

Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D05) Central limit and other weak theorems (60F05)

Review text

For i.i.d. random points \(X_1,\ldots ,X_n\) in \({\mathbb R}^d\) and \(0<p<1\), let \(L(X_1,\ldots ,X_n;p)\) be the minimum of \(\sum _{j=1}^n |X_{\pi (j+1)}-X_{\pi (j)} |^p\) over all permutations \(\pi \) of \(\{ 1,\ldots ,n\}\) (minimal path of the `travelling salesman'). The author shows that, under some regularity conditions posed on the distribution of the \(X_i\)'s, \(n^{(d-p)/d}L(X_1,\ldots ,X_n;p)\) converges to a given constant a.s. and in \(L^1\) (an analogous result was known earlier for \(p\geq 1\)). In fact, a more general result is proved, which yields as particular cases also the asymptotic behavior of the length of an optimal matching and of the length of a minimal spanning tree on \(X_1,\ldots ,X_n\).

Recommendations

• Worst case asymptotics of power-weighted Euclidean functionals
• Asymptotics for Euclidean functionals with power-weighted edges
• Asymptotics for weighted minimal spanning trees on random points
• Rates of convergence of means of Euclidean functionals
• scientific article; zbMATH DE number 4167872

Cites work

• Asymptotics for Euclidean functionals with power-weighted edges
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• Limit theorems and rates of convergence for Euclidean functionals
• Probability theory of classical Euclidean optimization problems

Cited in

(13)

• Growth rates of Euclidean minimal spanning trees with power weighted edges
• Rates of convergence of means for distance-minimizing subadditive Euclidean functionals
• Rate of convergence of power-weighted Euclidean minimal spanning trees
• Asymptotics for weighted minimal spanning trees on random points
• Worst case asymptotics of power-weighted Euclidean functionals
• Asymptotics for the Euclidean TSP with power weighted edges
• Asymptotics for Euclidean functionals with power-weighted edges
• Rates of convergence of means of Euclidean functionals
• scientific article; zbMATH DE number 4167872 (Why is no real title available?)
• Asymptotics for Euclidean functionals of mixing processes
• scientific article; zbMATH DE number 795116 (Why is no real title available?)
• Percolating paths through random points
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability

This page was built for publication: Asymptotic of power-weighted Euclidean functionals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1593589)