# Adapting k-means algorithms for outliers

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2020.

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

- [ADBench: Anomaly Detection Benchmark](https://mlsanity.com/paper/2206.09426/) (2022)
- [A Nearly Tight Analysis of Greedy k-means++](https://mlsanity.com/paper/2207.07949/) (2022)
- [TACTIC for Navigating the Unknown: Tabular Anomaly deteCTion via In-Context inference](https://mlsanity.com/paper/2603.14171/) (2026)
- [Modified K-means Algorithm with Local Optimality Guarantees](https://mlsanity.com/paper/2506.06990/) (2025)
- [Simple KNN-Based Outlier Detection Achieves Robust Clustering](https://mlsanity.com/paper/2605.07130/) (2026)
- [Randomizing the Number of Centers in k-means++](https://mlsanity.com/paper/2607.26202/) (2026)

## Abstract (arXiv)

This paper shows how to adapt several simple and classical sampling-based algorithms for the k-means problem to the setting with outliers. Recently, Bhaskara et al. (NeurIPS 2019) showed how to adapt the classical k-means++ algorithm to the setting with outliers. However, their algorithm needs to output O(log (k) · z) outliers, where z is the number of true outliers, to match the O(log k)-approximation guarantee of k-means++. In this paper, we build on their ideas and show how to adapt several sequential and distributed k-means algorithms to the setting with outliers, but with substantially stronger theoretical guarantees: our algorithms output (1+varepsilon)z outliers while achieving an O(1 / varepsilon)-approximation to the objective function. In the sequential world, we achieve this by adapting a recent algorithm of Lattanzi and Sohler (ICML 2019). In the distributed setting, we adapt a simple algorithm of Guha et al. (IEEE Trans. Know. and Data Engineering 2003) and the popular k-means| of Bahmani et al. (PVLDB 2012). A theoretical application of our techniques is an algorithm with running time tildeO(nk2/z) that achieves an O(1)-approximation to the objective function while outputting O(z) outliers, assuming k ll z ll n. This is complemented with a matching lower bound of Omega(nk2/z) for this problem in the oracle model.