Subadditive Euclidean Functionals and Nonlinear Growth in Geometric Probability

John Steele

Type: Article

Publication Date: 1981-06-01

Citations: 180

DOI: https://doi.org/10.1214/aop/1176994411

Abstract

A limit theorem is established for a class of random processes (called here subadditive Euclidean functionals) which arise in problems of geometric probability. Particular examples include the length of shortest path through a random sample, the length of a rectilinear Steiner tree spanned by a sample, and the length of a minimal matching. Also, a uniform convergence theorem is proved which is needed in Karp's probabilistic algorithm for the traveling salesman problem.

Locations

The Annals of Probability - View - PDF
ScholarlyCommons (University of Pennsylvania) - View - PDF

Similar Works

Action	Title	Year	Authors
+	A Matching Problem and Subadditive Euclidean Functionals	1993	Wansoo T. Rhee
+ PDF Chat	Large deviation principles for Euclidean functionals and other nearly additive processes	2001	Timo Seppäläinen J. E. Yukich
+ PDF Chat	Separating subadditive euclidean functionals	2016	Alan Frieze Wesley Pegden
+	Separating subadditive Euclidean functionals	2015	Alan Frieze Wesley Pegden
+	Separating subadditive Euclidean functionals	2015	Alan Frieze Wesley Pegden
+	Geometric and Functional Inequalities for Log-concave Probability Sequences	2020	Arnaud Marsiglietti James Melbourne
+ PDF Chat	Rates of Convergence of Means for Distance-Minimizing Subadditive Euclidean Functionals	1994	Kenneth S. Alexander
+ PDF Chat	Geometric and Functional Inequalities for Log-Concave Probability Sequences	2023	Arnaud Marsiglietti James Melbourne
+	Geometric properties of monotone functions and probabilities of random fluctuations	1996	V. V. Ivanov
+	Rates of convergence of means of Euclidean functionals	2006	Yooyoung Koo Sung Chul Lee
+	Constructing sublinear expectations on path space	2013	Marcel Nutz Ramon van Handel
+	Constructing Sublinear Expectations on Path Space	2013	Marcel Nutz Ramon van Handel
+ PDF Chat	Limit theorems with rate of convergence under sublinear expectations	2019	Xiao Fang Shigē Péng Qi-Man Shao Yongsheng Song
+ PDF Chat	Limit theory of combinatorial optimization for random geometric graphs	2021	Dieter Mitsche Mathew D. Penrose
+	Optimal transport methods for combinatorial optimization over two random point sets	2022	Michaël Goldman Dario Trevisan
+	Log-concave measures	2010	Denis Feyel A. S. Ustunel
+	Log-concave measures	2010	Denis Feyel Ali Süleyman Üstünel
+	Log-concave measures	2010	Denis Feyel A. S. Ustunel
+	Log-concave measures	2010	Denis Feyel A. S. Ustunel
+	Log-concave measures	2010	Denis Feyel A. S. Ustunel

Works That Cite This (87)

Action	Title	Year	Authors
+	The Traveling Salesman and Related Stochastic Problems	1998	Allon G. Percus
+	Martingale Inequalities, Interpolation and NP-Complete Problems	1989	Wansoo T. Rhee Michel Talagrand
+	Steinhaus's geometric location problem for random samples in the plane	1982	Dorit S. Hochbaum John Steele
+	Rates of convergence of means of Euclidean functionals	2006	Yooyoung Koo Sung Chul Lee
+ PDF Chat	Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted Edges	1988	John Steele
+	A survey of heuristics for the weighted matching problem	1983	David Avis
+ PDF Chat	Rates of Convergence of Means of Euclidean Functionals	2007	Yooyoung Koo Sung Chul Lee
+	The Law of the Iterated Logarithm for the Total Length of the Nearest Neighbor Graph	2004	Young-Hoon Kim Sung Chul Lee Zhengyan Lin
+	The Invariance Principle for the Total Length of the Nearest-Neighbor Graph	2005	Young-Hoon Kim Sung Chul Lee Zhengyan Lin Wensheng Wang
+ PDF Chat	On minimum spanning trees for random Euclidean bipartite graphs	2023	Mario Correddu Dario Trevisan

Works Cited by This (6)

Action	Title	Year	Authors
+ PDF Chat	Empirical Discrepancies and Subadditive Processes	1978	John Steele
+ PDF Chat	Postulates for Subadditive Processes	1974	J. M. Hammersley
+	�ber einen geometrischen Satz	1940	László Fejes
+ PDF Chat	A Lower Bound for the Expected Travel Among $m$ Random Points	1948	Eli S. Marks
+ PDF Chat	Relations between Weak and Uniform Convergence of Measures with Applications	1962	R. Ranga Rao
+ PDF Chat	Complete Convergence of Short Paths and Karp's Algorithm for the TSP	1981	John Steele