Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-24T14:02:34.238Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotics for geometric location problems over random samples

Part of: Graph theory Geometric probability and stochastic geometry Operations research and management science Limit theorems

Published online by Cambridge University Press:  01 July 2016

K. McGivney  and
J. E. Yukich
K. McGivney*
Affiliation:
University of Arizona
J. E. Yukich*
Affiliation:
Lehigh University
*
∗ Postal address: Department of Mathematics, The University of Arizona, Building 89, 617 N Santa Rita, Tucson, AZ 85721, USA. Email address: [email protected]
∗∗ Postal address: Department of Mathematics, Lehigh University, Bethlehem, PA 18015, USA. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider the basic location problem in which k locations from among n given points X1,…,Xn are to be chosen so as to minimize the sum M(k; X1,…,Xn) of the distances of each point to the nearest location. It is assumed that no location can serve more than a fixed finite number D of points. When the Xi, i ≥ 1, are i.i.d. random variables with values in [0,1]d and when k = ⌈n/(D+1)⌉ we show that

where α := α(D,d) is a positive constant, f is the density of the absolutely continuous part of the law of X1, and c.c. denotes complete convergence.

Keywords

k-median problemsubadditive Euclidean functionalboundary functionallocation problems

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry 60F15: Strong theorems
Secondary: 05C80: Random graphs 90B80: Discrete location and assignment
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 31 , Issue 3 , September 1999 , pp. 632 - 642
Copyright
Copyright © Applied Probability Trust 1999 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Research supported in part by NSA grant MDA904-95-H-1005.

References

Courant, R. and Robbins, H. (1941). What is Mathematics? Oxford University Press, Oxford.Google Scholar
Fisher, M. L. and Hochbaum, D. S. (1980). Probabilistic analysis of the planar K-median problem. Math. Operat. Res. 5, 27–34.CrossRefGoogle Scholar
Hochbaum, D. and Steele, J. M. (1982). Steinhaus's geometric location problem for random samples in the plane. Adv. Appl. Prob. 14, 55–67.CrossRefGoogle Scholar
Kuhn, H. W. (1974). ‘Steiner's’ problem revisited. In Studies in optimization (Studies in Mathematics 10), eds. Dantzig, G. B. and Eaves, B. C.. MAA, Washington, pp. 52–70,Google ScholarPubMed
Papadimitriou, C.H. (1981). Worst-case and probabilistic analysis of a geometric location problem. SIAM J. Comput. 10, 542–557.CrossRefGoogle Scholar
Redmond, C. and Yukich, J. E. (1994). Limit theorems and rates of convergence for subadditive Euclidean functionals. Ann. Appl. Prob. 4, 1057–1073.CrossRefGoogle Scholar
Redmond, C. and Yukich, J. E. (1996). Asymptotics for Euclidean functionals with power weighted edges. Stoch. Proc. Appl. 61, 289–304.CrossRefGoogle Scholar
Steele, J.M. (1981). Subadditive Euclidean functionals and non-linear growth in geometric probability. Ann. Prob. 9, 365–376.CrossRefGoogle Scholar
Steinhaus, H. (1956). Sur la division de corps matériels en parties, Bull. Acad. Polon. Sci. 4, 801–804.Google Scholar
Yukich, J. E. (1998). Probability Theory of Classical Euclidean Optimization Problems (Lecture Notes in Math. 1675). Springer, Berlin.Google Scholar