Geometric Facility Location Problems on Uncertain Data

摘要

In this dissertation, we study several facility location problems on uncertain data. We mainly consider the k-center problem and many of its variations. These are classical problems in computer science and operations research. These problems on deterministic data have been studied extensively in the literature. We consider them on uncertain data because data in the real world is often associated with uncertainty due to measurement inaccuracy, sampling discrepancy, outdated data sources, resource limitation, etc. Although we focus on the theoretical study, the algorithms developed in this dissertation may find applications in other areas such as data clustering, wireless sensor locations, object classification, etc. In our problems, the input consists of uncertain points each of which has multiple locations following a probability density function (pdf). Specifically, we first study the k-center problem on uncertain points on a line to compute kcenters to minimize the maximum expected distance from all uncertain points to their expected closest centers. We consider two cases of the uncertainty: the continuous case and the discrete case. In the continuous case, the location of every uncertain point follows a continuous piecewise-uniform pdf, whereas in the discrete case, each uncertain point has multiple discrete locations each associated with a probability. We then consider the one-center problem (i.e., k = 1) on a tree, where each uncertain point has multiple discrete locations in the tree and we want to compute a center in the tree to minimize the maximum expected distance from it to all uncertain points. Next, we consider the one-dimensional one-center problem of uncertain points with continuous pdfs, and the one-center problem in the plane under the rectilinear metric for uncertain points with discrete locations. In addition, we study the more general k-center problem on uncertain points in a tree. Finally, we consider the line-constrained k-center problem on deterministic points in the plane with the constraint that the centers are required to be located on a given line. Several distance metrics including L 1, L2, and Linfinity are considered. We also study the line-constrained k-median and k-means problems in the plane. Based on interesting problem modeling and observations, we develop efficient algorithms for solving these problems with the help of computational geometry techniques. Some of our algorithms have time complexities either linear or nearly linear. Others al-most match those for the same problems on deterministic data or improve the previous work. The algorithms, data structures, and techniques developed in this dissertation may be used to solve other related problems as well.