Dynamic Consistent k -Center Clustering with Optimal Recourse
Sebastian Forster, Antonis Skarlatos · Society for Industrial and Applied Mathematics eBooks · 2025
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 k-clustering problem? This question has received attention in recent years under the name consistent clustering.