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 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 P 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. (C) 2015 Elsevier B.V. All rights reserved.