Balancing Distance and Choice: \((k,\alpha)\)-Center Clustering

Abstract

In this work, we examine a variant of \(k\)-center that allows for fault tolerance based on an input parameter \(\alpha\). Here, each client cares about its distance to the \(\alpha\)th closest center. This is slightly different than similar variants that have been presented in prior work, and this necessitates different machinery. In particular, we show an elegant \(2\)-approximation algorithm for this problem, and how this algorithm can be sped up to run in linear  time. Finally, we present an algorithm computing a greedy \(\alpha\)-permutation that provides this approximation for all \(k\), and this algorithm runs in \(O(n \log n)\) time (if \(\alpha\) and the doubling dimension are constant). We thus establish that \((k,\alpha)\)-center clustering and the "regular" \(k\)-center clustering have the same approximation complexity.