# Approximation algorithm for the kinetic robust K-center problem

Title | Approximation algorithm for the kinetic robust K-center problem |

Publication Type | Journal Articles |

Year of Publication | 2010 |

Authors | Friedler SA, Mount D |

Journal | Computational Geometry |

Volume | 43 |

Issue | 6–7 |

Pagination | 572 - 586 |

Date Published | 2010/08// |

ISBN Number | 0925-7721 |

Keywords | Approximation 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. |

URL | http://www.sciencedirect.com/science/article/pii/S0925772110000027 |

DOI | 10.1016/j.comgeo.2010.01.001 |