@article {15566,
title = {Approximation algorithm for the kinetic robust K-center problem},
journal = {Computational Geometry},
volume = {43},
year = {2010},
month = {2010/08//},
pages = {572 - 586},
abstract = {Two complications frequently arise in real-world applications, motion and the contamination of data by outliers. We consider a fundamental clustering problem, the k-center problem, within the context of these two issues. We are given a finite point set S of size n and an integer k. In the standard k-center problem, the objective is to compute a set of k center points to minimize the maximum distance from any point of S to its closest center, or equivalently, the smallest radius such that S can be covered by k disks of this radius. In the discrete k-center problem the disk centers are drawn from the points of S, and in the absolute k-center problem the disk centers are unrestricted.We generalize this problem in two ways. First, we assume that points are in continuous motion, and the objective is to maintain a solution over time. Second, we assume that some given robustness parameter 0 \< t ⩽ 1 is given, and the objective is to compute the smallest radius such that there exist k disks of this radius that cover at least ⌈ t n ⌉ points of S. We present a kinetic data structure (in the KDS framework) that maintains a ( 3 + ε ) -approximation for the robust discrete k-center problem and a ( 4 + ε ) -approximation for the robust absolute k-center problem, both under the assumption that k is a constant. We also improve on a previous 8-approximation for the non-robust discrete kinetic k-center problem, for arbitrary k, and show that our data structure achieves a ( 4 + ε ) -approximation. All these results hold in any metric space of constant doubling dimension, which includes Euclidean space of constant dimension.
},
keywords = {Approximation algorithms, clustering, kinetic data structures, robust statistics},
isbn = {0925-7721},
doi = {10.1016/j.comgeo.2010.01.001},
url = {http://www.sciencedirect.com/science/article/pii/S0925772110000027},
author = {Friedler,Sorelle A. and Mount, Dave}
}