Rates of convergence of means of Euclidean functionals

DOI10.1007/S10959-007-0089-7zbMATH Open1153.60017arXivmath/0609382OpenAlexW2087384730MaRDI QIDQ2471129FDOQ2471129

Authors: Yoo Young Koo, Sungchul Lee 

Publication date: 18 February 2008

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

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}$.

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

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

zbMATH Keywords

rate of convergencetraveling salesman problemEuclidean functionals

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

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