Almost Optimal Fully Dynamic k-Center Clustering with Recourse

In this paper, we consider the metric k-center problem in the fully dynamic setting, where we are given a metric space (V, d) evolving via a sequence of point insertions and deletions and our task is to maintain a subset S ⊆ V of at most k points that minimizes the objective max x∈V min y∈S d(x, y). We want to design our algorithm so that we minimize its approximation ratio, recourse (the number of changes it makes to the solution S) and update time (the time it takes to handle an update). We give a simple algorithm for dynamic k-center that maintains a O(1)-approximate solution with O(1) amortized recourse and Õ(k) amortized update time, obtaining near-optimal approximation, recourse and update time simultaneously. We obtain our result by combining a variant of the dynamic k-center algorithm of Bateni et al. [SODA'23] with the dynamic sparsifier of Bhattacharya et al. [NeurIPS'23].