One-dimensional k-center on uncertain data

Problems on uncertain data have attracted significant attention due to the imprecise nature of many measurement data. In this paper, we consider the k  -center problem on one-dimensional uncertain data. The input is a set PP of (weighted) uncertain points on a real line, and each uncertain point is specified by its probability density function (pdf) which is a piecewise-uniform function (i.e., a histogram). The goal is to find a set Q of k   points on the line to minimize the maximum expected distance from the uncertain points of PP to their expected closest points in Q. We present efficient algorithms for this uncertain k-center problem and their running times almost match those for the “deterministic” k-center problem.