Dynamic clustering keeps centers updated fast with limited changes
Dynamic $k$-Median with Worst-Case Update Time and Recourse
Data Structures and Algorithms
Summary
The paper looks at how to quickly update group centers when points are added or removed from a space, like choosing store locations as customers come and go. The authors create a method that always keeps the number of centers small and close to optimal, while making only a few center changes each time. Their approach works reliably for any sequence of updates and runs efficiently even in the worst cases. They also adapt their method to a related grouping problem called k-means.
What this means in practice
- •For network planners: Maintain efficient network hub locations when clients join or leave rapidly with minimal service disruptions.
- •For online retail teams: Adjust physical store or warehouse locations adaptively as customer distributions change over time with fast updates and few relocations.
Authors
Chenglin Fan
Abstract
We study fully dynamic metric $k$-median under unit-weight client insertions and deletions. After each update, the algorithm must maintain at most $k$ centers chosen from the current client locations. We give a randomized constant-factor approximation algorithm with $\widetilde O(k)$ worst-case update time and $O((1+\logΔ)^3)$ worst-case center recourse, where $Δ$ is the aspect ratio of the underlying metric space. The approximation guarantee holds simultaneously over any prescribed finite adaptive update sequence with high probability, while the update time and recourse bounds hold on every execution. We also obtain the same asymptotic guarantees for metric $k$-means.