Approximation algorithm for the kinetic robust K-center problem

TitleApproximation algorithm for the kinetic robust K-center problem
Publication TypeJournal Articles
Year of Publication2010
AuthorsFriedler SA, Mount D
JournalComputational Geometry
Volume43
Issue6–7
Pagination572 - 586
Date Published2010/08//
ISBN Number0925-7721
KeywordsApproximation algorithms, clustering, kinetic data structures, robust statistics
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.

URLhttp://www.sciencedirect.com/science/article/pii/S0925772110000027
DOI10.1016/j.comgeo.2010.01.001