# A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 35 references that are in the map.
- First posted on arXiv 8 Feb 2021.

## Builds on (most cited first, 5 of 5)

- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [An Algorithm for Online K-Means Clustering](https://mlsanity.com/paper/1412.5721/) (2014)
- [Sequential no-Substitution k-Median-Clustering](https://mlsanity.com/paper/1905.12925/) (2019)
- [No-substitution k-means Clustering with Adversarial Order](https://mlsanity.com/paper/2012.14512/) (2020)
- [Unexpected Effects of Online no-Substitution k-means Clustering](https://mlsanity.com/paper/1908.06818/) (2019)

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

- [Online k-means Clustering on Arbitrary Data Streams](https://mlsanity.com/paper/2102.09101/) (2021)
- [Fast Distributed k-Means with a Small Number of Rounds](https://mlsanity.com/paper/2201.13217/) (2022)

## Abstract (arXiv)

We study k-median clustering under the sequential no-substitution setting. In this setting, a data stream is sequentially observed, and some of the points are selected by the algorithm as cluster centers. However, a point can be selected as a center only immediately after it is observed, before observing the next point. In addition, a selected center cannot be substituted later. We give the first algorithm for this setting that obtains a constant approximation factor on the optimal risk under a random arrival order, an exponential improvement over previous work. This is also the first constant approximation guarantee that holds without any structural assumptions on the input data. Moreover, the number of selected centers is only quasi-linear in k. Our algorithm and analysis are based on a careful risk estimation that avoids outliers, a new concept of a linear bin division, and a multiscale approach to center selection.