In this paper, we consider the rectilinear one-center problem on uncertain points in the plane. In this problem, we are given a set @math of @math (weighted) uncertain points in the plane and each uncertain point has @math possible locations each associated with a probability for the point appearing at that location. The goal is to find a point @math in the plane which minimizes the maximum expected rectilinear distance from @math to all uncertain points of @math , and @math is called a rectilinear center. We present an algorithm that solves the problem in @math time. Since the input size of the problem is @math , our algorithm is optimal.
Center problems or minimax facility location problems are among the most active research areas in location theory. In this paper, we find the best unique location for a facility in the plane such that the maximum expected weighted distance to all random demand points is minimized. There is an increasing quantity of data with uncertainty arising from applications such as sensor network measurements, record linkage, and as output of mining algorithms. This uncertainty is typically formalized as probability density functions over tuple values. Beyond storing and processing such data in a DBMS, it is necessary to perform other data analysis tasks such as data mining. We study the core mining problem of clustering on uncertain data, and define appropriate natural generalizations of standard clustering optimization criteria. Two variations arise, depending on whether a point is automatically associated with its optimal center, or whether it must be assigned to a fixed cluster no matter where it is actually located. For uncertain versions of k-means and k-median, we show reductions to their corresponding weighted versions on data with no uncertainties. These are simple in the unassigned case, but require some care for the assigned version. Our most interesting results are for uncertain k-center, which generalizes both traditional k-center and k-median objectives. We show a variety of bicriteria approximation algorithms. One picks O(ke--1log2n) centers and achieves a (1 + e) approximation to the best uncertain k-centers. Another picks 2k centers and achieves a constant factor approximation. Collectively, these results are the first known guaranteed approximation algorithms for the problems of clustering uncertain data. 