Abstract
Given points from an arbitrary metric space and a sequence of point updatessent by an adversary, what is the minimum recourse per update (i.e., theminimum number of changes needed to the set of centers after an update), inorder to maintain a constant-factor approximation to a $k$-clustering problem?This question has received attention in recent years under the name consistentclustering. Previous works by Lattanzi and Vassilvitskii [ICLM '17] and Fichtenberger,Lattanzi, Norouzi-Fard, and Svensson [SODA '21] studied $k$-clusteringobjectives, including the $k$-center and the $k$-median objectives, under onlypoint insertions. In this paper we study the $k$-center objective in the fullydynamic setting, where the update is either a point insertion or a pointdeletion. Before our work, {\L}\k{a}cki, Haeupler, Grunau, Rozho\v{n}, andJayaram [SODA '24] gave a deterministic fully dynamic constant-factorapproximation algorithm for the $k$-center objective with worst-case recourseof $2$ per update. In this work, we prove that the $k$-center clustering problem admits optimalrecourse bounds by developing a deterministic fully dynamic constant-factorapproximation algorithm with worst-case recourse of $1$ per update. Moreoverour algorithm performs simple choices based on light data structures, and thusis arguably more direct and faster than the previous one which uses asophisticated combinatorial structure. Additionally, we develop a newdeterministic decremental algorithm and a new deterministic incrementalalgorithm, both of which maintain a $6$-approximate $k$-center solution withworst-case recourse of $1$ per update. Our incremental algorithm improves overthe $8$-approximation algorithm by Charikar, Chekuri, Feder, and Motwani [STOC'97]. Finally, we remark that since all three of our algorithms aredeterministic, they work against an adaptive adversary.