# Consistent k-Median: Simpler, Better and Robust

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 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)
- [Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals](https://mlsanity.com/paper/2601.16091/) (2026)
- [A General Framework for Dynamic Consistent Submodular Maximization](https://mlsanity.com/paper/2606.04946/) (2026)
- [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)

In this paper we introduce and study the online consistent k-clustering with outliers problem, generalizing the non-outlier version of the problem studied in [Lattanzi-Vassilvitskii, ICML17]. We show that a simple local-search based online algorithm can give a bicriteria constant approximation for the problem with O(k2 log2 (nD)) swaps of medians (recourse) in total, where D is the diameter of the metric. When restricted to the problem without outliers, our algorithm is simpler, deterministic and gives better approximation ratio and recourse, compared to that of [Lattanzi-Vassilvitskii, ICML17].