Asymptotic of power-weighted Euclidean functionals
type: Item
instance of: scholarly article
title: Asymptotic of power-weighted Euclidean functionals
zbMATH Open document ID: 0961.60018
DOI: 10.1016/S0304-4149(98)00065-9
author: Sungchul Lee
published in: Stochastic Processes and their Applications
publication date: 2001-01-17T00:00:00Z
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\).
reviewed by: Jan Rataj
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 60F05
zbMATH DE Number: 1554276
zbMATH Keywords: travelling salesman problem
zbMATH Keywords: minimal matching
zbMATH Keywords: minimal spanning tree
zbMATH Keywords: strong law of large numbers
MaRDI profile type: Publication
cites work: Q5729634
cites work: Limit theorems and rates of convergence for Euclidean functionals
cites work: Asymptotics for Euclidean functionals with power-weighted edges
cites work: Growth rates of Euclidean minimal spanning trees with power weighted edges
cites work: Q5691080
cites work: Probability theory of classical Euclidean optimization problems
full work available at URL: s0304-4149(98)00065-9
OpenAlex ID: W2037534835
description: scientific article; zbMATH DE number 1554276