# Consistent k-Clustering for General Metrics

arXiv: https://arxiv.org/abs/2011.06888 · HTML: https://mlsanity.com/paper/2011.06888/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2020.

## Built on by (most cited first, 7 of 7)

- [Consistent Submodular Maximization](https://mlsanity.com/paper/2405.19977/) (2024)
- [Dynamic Correlation Clustering in Sublinear Update Time](https://mlsanity.com/paper/2406.09137/) (2024)
- [The Cost of Consistency: Submodular Maximization with Constant Recourse](https://mlsanity.com/paper/2412.02492/) (2024)
- [Label-consistent clustering for evolving data](https://mlsanity.com/paper/2512.15210/) (2025)
- [Dynamic algorithms for k-center on graphs](https://mlsanity.com/paper/2307.15557/) (2023)
- [Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms](https://mlsanity.com/paper/2510.15076/) (2025)
- [Clustering with Label Consistency](https://mlsanity.com/paper/2512.19654/) (2025)

## Abstract (arXiv)

Given a stream of points in a metric space, is it possible to maintain a constant approximate clustering by changing the cluster centers only a small number of times during the entire execution of the algorithm? This question received attention in recent years in the machine learning literature and, before our work, the best known algorithm performs widetildeO(k2) center swaps (the widetildeO(·) notation hides polylogarithmic factors in the number of points n and the aspect ratio Delta of the input instance). This is a quadratic increase compared to the offline case -- the whole stream is known in advance and one is interested in keeping a constant approximation at any point in time -- for which widetildeO(k) swaps are known to be sufficient and simple examples show that Omega(k log(n Delta)) swaps are necessary. We close this gap by developing an algorithm that, perhaps surprisingly, matches the guarantees in the offline setting. Specifically, we show how to maintain a constant-factor approximation for the k-median problem by performing an optimal (up to polylogarithimic factors) number widetildeO(k) of center swaps. To obtain our result we leverage new structural properties of k-median clustering that may be of independent interest.