Provides a probabilistic analysis of the linear programming (LP) relaxation of the k-median problem when the number of points goes to infinity. Background on the k-median problem; Way in which LP relaxation is obtained; Results of computational experiments.