Dynamic Consistent k-Center Clustering with Optimal Recourse

Given points from an arbitrary metric space and a sequence of point updates sent by an adversary, what is the minimum recourse per update (i.e., the minimum number of changes needed to the set of centers after an update), in order to maintain a constant-factor approximation to a 𝑘-clustering problem? This question has received attention in recent years under the name consistent clustering.

Previous works by Lattanzi and Vassilvitskii [ICLM '17] and Fichtenberger, Lattanzi, Norouzi-Fard, and Svensson [SODA '21] studied 𝑘-clustering objectives, including the 𝑘-center and the 𝑘-median objectives, under only point insertions. In this paper we study the 𝑘-center objective in the fully dynamic setting, where the update is either a point insertion or a point deletion. Before our work, Łącki r ⃝ Haeupler r ⃝ Grunau r ⃝ Rozhoň r ⃝ Jayaram [SODA '24] gave a deterministic fully dynamic constant-factor approximation algorithm for the 𝑘-center objective with worst-case recourse of 2 per point update (i.e., point insertion/point deletion).

In this work, we prove that the 𝑘-center clustering problem admits optimal recourse bounds by developing a deterministic fully dynamic constant-factor approximation algorithm with worst-case recourse of 1 per point update. Moreover our algorithm performs simple choices based on light data structures, and thus is arguably more direct and faster than the previous one which uses a sophisticated combinatorial structure. Additionally to complete the picture, we develop a new deterministic decremental algorithm and a new deterministic incremental algorithm, both of which maintain a 6-approximate 𝑘-center solution with worst-case recourse of 1 per point update. Our incremental algorithm improves over the 8-approximation algorithm by Charikar, Chekuri, Feder, and Motwani [STOC '97]. Finally, we remark that since all three of our algorithms are deterministic, they work against an adaptive adversary.