Asymptotics for geometric location problems over random samples

摘要

Consider the basic location problem in which k locations from among n given points X-1,..., X-n are to be chosen so as to minimize the sum M(k; X-1,..., X-n) 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 X-i, i greater than or equal to 1, are i.i.d. random variables with values in [0, 1](d) and when k = inverted right perpendicularn/(D + 1)inverted left perpendicular we show that [GRAPHICS] where alpha := alpha(D, d) is a positive constant, f is the density of the absolutely continuous part of the law of X-1, and c.c. denotes complete convergence. [References: 10]