# Sets Clustering

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2020.

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [Coresets for Decision Trees of Signals](https://mlsanity.com/paper/2110.03195/) (2021)
- [Dataset Distillation Meets Provable Subset Selection](https://mlsanity.com/paper/2307.08086/) (2023)
- [Coresets for Data Discretization and Sine Wave Fitting](https://mlsanity.com/paper/2203.03009/) (2022)
- [Obstacle Aware Sampling for Path Planning](https://mlsanity.com/paper/2203.04075/) (2022)
- [An Efficient Drifters Deployment Strategy to Evaluate Water Current Velocity Fields](https://mlsanity.com/paper/2301.04216/) (2023)
- [DataS^3: Dataset Subset Selection for Specialization](https://mlsanity.com/paper/2504.16277/) (2025)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)
- [ORBSLAM3-Enhanced Autonomous Toy Drones: Pioneering Indoor Exploration](https://mlsanity.com/paper/2312.13385/) (2023)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [On the Size and Approximation Error of Distilled Sets](https://mlsanity.com/paper/2305.14113/) (2023)
- [Provable Pruning for Efficient 3D Gaussian Splatting via Coresets](https://mlsanity.com/paper/2607.02721/) (2026)
- [Improving Model Classification by Optimizing the Training Dataset](https://mlsanity.com/paper/2507.16729/) (2025)
- [Linear time small coresets for k-mean clustering of segments with applications](https://mlsanity.com/paper/2511.12564/) (2025)
- [Fair Dataset Distillation via Cross-Group Barycenter Alignment](https://mlsanity.com/paper/2605.00185/) (2026)

## Abstract (arXiv)

The input to the sets-k-means problem is an integer k≥ 1 and a set P=P1,cdots,Pn of sets in ℝd. The goal is to compute a set C of k centers (points) in ℝd that minimizes the sum sumP∈ P minp∈ P, c∈ Cleft| p-c right|2 of squared distances to these sets. An varepsilon-core-set for this problem is a weighted subset of P that approximates this sum up to 1±varepsilon factor, for every set C of k centers in ℝd. We prove that such a core-set of O(log2n) sets always exists, and can be computed in O(nlogn) time, for every input P and every fixed d,k≥ 1 and varepsilon ∈ (0,1). The result easily generalized for any metric space, distances to the power of z>0, and M-estimators that handle outliers. Applying an inefficient but optimal algorithm on this coreset allows us to obtain the first PTAS (1+varepsilon approximation) for the sets-k-means problem that takes time near linear in n. This is the first result even for sets-mean on the plane (k=1, d=2). Open source code and experimental results for document classification and facility locations are also provided.