Rates of convergence of means of Euclidean functionals

DOI10.1007/S10959-007-0089-7MaRDI QIDQ2471129zbMATH OpenOpenAlexFDO

Authors Yoo Young Koo, Sungchul Lee

Publication date 18 February 2008

Published in Journal of Theoretical Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609382

zbMATH Keywords

rate of convergencetraveling salesman problemEuclidean functionals

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Strong limit theorems (60F15)

Abstract: Let $L$ be the Euclidean functional with $p$-th power-weighted edges. Examples include the sum of the $p$-th power-weighted lengths of the edges in minimal spanning trees, traveling salesman tours, and minimal matchings. Motivated by the works of Steele, Redmond and Yukich (1994, 1996) have shown that for $n$ i.i.d. sample points $X_1,\mathrm{...},X_n$ from $[0,1{]}^d$, $L(X_1,\mathrm{...},X_n)/n^{(d-p)/d}$ converges a.s. to a finite constant. Here we bound the rate of convergence of $EL(X_1,\mathrm{...},X_n)/n^{(d-p)/d}$.

Recommendations

• Rates of convergence of means for distance-minimizing subadditive Euclidean functionals
• Rates of Convergence for Quasi-Additive Smooth Euclidean Functionals and Application to Combinatorial Optimization Problems
• Asymptotics for Euclidean functionals with power-weighted edges
• Rate of convergence of power-weighted Euclidean minimal spanning trees
• Asymptotic of power-weighted Euclidean functionals

Cites work

• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• Asymptotic of power-weighted Euclidean functionals
• Asymptotics for Euclidean functionals with power-weighted edges
• Boundary effects in the traveling salesperson problem
• Complete Convergence of Short Paths and Karp's Algorithm for the TSP
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• Limit theorems and rates of convergence for Euclidean functionals
• Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
• Probability theory of classical Euclidean optimization problems
• Rate of convergence for the Euclidean minimum spanning tree limit law
• Rate of convergence of power-weighted Euclidean minimal spanning trees
• Rates of convergence of means for distance-minimizing subadditive Euclidean functionals
• Subadditive Euclidean functionals and nonlinear growth in geometric probability

Cited in

(9)

• Worst case asymptotics of power-weighted Euclidean functionals
• Rate of convergence of the mean for sub-additive ergodic sequences
• Limit theorems in discrete stochastic geometry
• Rates of convergence of means for distance-minimizing subadditive Euclidean functionals
• Convergence Rate for Degenerate von Mises Functionals
• Asymptotic of power-weighted Euclidean functionals
• Rate of convergence of power-weighted Euclidean minimal spanning trees
• Strong laws for Euclidean graphs with general edge weights
• Limit theorems and rates of convergence for Euclidean functionals

This page was built for publication: Rates of convergence of means of Euclidean functionals

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