# Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 14 Jun 2021.

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

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [varepsilon-Coresets for Clustering (with Outliers) in Doubling Metrics](https://mlsanity.com/paper/1804.02530/) (2018)
- [On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications](https://mlsanity.com/paper/2007.10137/) (2020)
- [Faster Algorithms for the Constrained k-means Problem](https://mlsanity.com/paper/1504.02564/) (2015)
- [A Unified Framework for Clustering Constrained Data without Locality Property](https://mlsanity.com/paper/1810.01049/) (2018)
- [Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers](https://mlsanity.com/paper/1608.01700/) (2016)
- [Coresets for k-Means and k-Median Clustering and their Applications](https://mlsanity.com/paper/1810.12826/) (2018)

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

- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering](https://mlsanity.com/paper/2601.20157/) (2026)

## Abstract (arXiv)

We study (Euclidean) k-median and k-means with constraints in the streaming model. There have been recent efforts to design unified algorithms to solve constrained k-means problems without using knowledge of the specific constraint at hand aside from mild assumptions like the polynomial computability of feasibility under the constraint (compute if a clustering satisfies the constraint) or the presence of an efficient assignment oracle (given a set of centers, produce an optimal assignment of points to the centers which satisfies the constraint). These algorithms have a running time exponential in k, but can be applied to a wide range of constraints. We demonstrate that a technique proposed in 2019 for solving a specific constrained streaming k-means problem, namely fair k-means clustering, actually implies streaming algorithms for all these constraints. These work for low dimensional Euclidean space. [Note that there are more algorithms for streaming fair k-means today, in particular they exist for high dimensional spaces now as well.]