Fully Dynamic Consistent k -Center Clustering
Jakub Łącki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram, Václav Rozhoň · Society for Industrial and Applied Mathematics eBooks · 2024
We study the consistent k-center clustering problem. In this problem, the goal is to maintain a constant factor approximate k-center solution during a sequence of n point insertions and deletions while minimizing the recourse, i.e., the number of changes made to the set of centers after each point insertion or deletion. Previous works by Lattanzi and Vassilvitskii [ICML ‘12] and Fichtenberger, Lattanzi, Norouzi-Fard, and Svensson [SODA ‘21] showed that in the incremental setting, where deletions are not allowed, one can obtain k · polylog(n)/n amortized recourse for both k-center and k-median, and demonstrated a matching lower bound. However, no algorithm for the fully dynamic setting achieves less than the trivial O(k) changes per update, which can be obtained by simply reclustering the full dataset after every update.