2013/07/09 by Nirman Kumar, Kumar, Nirman, Benjamin Raichel +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1307.2520
arxiv created 2013/07/09 · openalex publication_date 2013/07/09 · arxiv updated 2013/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In discrete k-center and k-median clustering, we are given a set of points P in a metric space M, and the task is to output a set C ⊆ ? P, |C| = k, such that the cost of clustering P using C is as small as possible. For k-center, the cost is the furthest a point has to travel to its nearest center, whereas for k-median, the cost is the sum of all point to nearest center distances. In the fault-tolerant versions of these problems, we are given an additional parameter 1 ?≤ ℓ ≤ ? k, such that when computing the cost of clustering, points are assigned to their ℓ-th nearest-neighbor in C, instead of their nearest neighbor. We provide constant factor approximation algorithms for these problems that are both conceptually simple and highly practical from an implementation stand-point.