# Coresets for k-Means and k-Median Clustering and their Applications

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

## Key facts

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

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

- [Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space](https://mlsanity.com/paper/2106.07319/) (2021)
- [Deterministic Coreset Construction via Adaptive Sensitivity Trimming](https://mlsanity.com/paper/2508.18340/) (2025)

## Abstract (arXiv)

renewcommandRerm I!hspace-0.025em R newcommandepsvarepsilon newcommandCoresetS  In this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. In other words, we show that given a point set P in Red, one can compute a weighted set Coreset subseteq P, of size O(k eps-d logn), such that one can compute the k-median/means clustering on Coreset instead of on P, and get an (1+eps)-approximation. As a result, we improve the fastest known algorithms for (1+eps)-approximate k-means and k-median clustering. Our algorithms have linear running time for a fixed k and eps. In addition, we can maintain the (1+eps)-approximate k-median or k-means clustering of a stream when points are being only inserted, using polylogarithmic space and update time.