Mathematics of Operations Research May 1989 [antikvár]

MATHEMATICS OF OPERATIONS RESEARCH Vol. 14. No. 2. May 1989 PrhiteJ in U.S.^. A CONCENTRATION INEQUALITY FOR THE i(:-MEDIAN PROBLEM* wansoo t. rheet AND michel talagrand* We use the theory of empirical processes to analyze a stochastic version of the AT-median problem. 1. Introduction. Let be points in the m-dimensional space R". (These points are often referred to as customers.) The A^-median problem is the problem of finding points Ci, , c^ (referred to as centers) so as to minimize the total sum of the distances between customers and their closest center, i.e. rliii ¦mm II I ! ' ¦ ¦ , • * i L Minll sw J'f^ We consider here a free version of the problem, i.e. we do not require centers to be located only at customer locations, but we require them to be located in some fixed bounded closed set 'if. The .K-median problem is known to be JVP-complete ([3], [9]), so it is likely to be hard to solve. As is the case with other iVP-complete problems, researchers have investigated stochastic versions of the problem ([2], [5], [6]). We are interested here in the very general model where the customers X^, , X^ are independently distributed according to some probability distribution !i. We assume that is supported by 'i, i.e., = 1, but we can obtain results even without any regularity assumptions on !i. We denote by Qf;{X^, , Xj^) the optimum value of the i^-median problem for customers X^, ,Xff (the set being fixed independently of Xj, , X^), that is. Researchers have noted that associated to the stochastic problem is a deterministic continuous problem ([4], [6]), viz., finding <2^(ju) = Min /Min||x - cjrf^t(x): I y < ^ They have proved that under certain circumstances the asymptotic behaviors of Qk(.X^, , Xfj) and Q^iiJ.) are similar when K and N co. The aim of this paper is •Received November 7, 1986; revised October 20, 1987. AMS 1980 subject classification. Primary: 68C25. Secondary: 65K05, 60D05, 60F10. lAOR 1973 subject classification. Main: Distribution. Cross references: Probability. OR/MS Index 1978 subject classification. Primary: 185 Facilities/equipment planning/location. Secondary: 561 Probability. Key words. Empirical process, stochastic A'-median problem. *Ohio State University * Université de Paris VL 189 0364-765X/89/1402/0189$01.25 Copyright © 1989. The Institute of Management Seicnces/Operations Research Society of America f ¦ 1 ¦•; ¦"'.i.'i;-' 344