# Universal Weak Coreset

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 26 references that are in the map.
- First posted on arXiv 26 May 2023.

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

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [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)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [Coresets for Clustering in Excluded-minor Graphs and Beyond](https://mlsanity.com/paper/2004.07718/) (2020)
- [Coresets for Clustering in Graphs of Bounded Treewidth](https://mlsanity.com/paper/1907.04733/) (2019)
- [A Unified Framework for Clustering Constrained Data without Locality Property](https://mlsanity.com/paper/1810.01049/) (2018)
- [FPT Approximation for Constrained Metric k-Median/Means](https://mlsanity.com/paper/2007.11773/) (2020)
- [Clustering Permutations: New Techniques with Streaming Applications](https://mlsanity.com/paper/2212.01821/) (2022)

## Abstract (arXiv)

Coresets for k-means and k-median problems yield a small summary of the data, which preserve the clustering cost with respect to any set of k centers. Recently coresets have also been constructed for constrained k-means and k-median problems. However, the notion of coresets has the drawback that (i) they can only be applied in settings where the input points are allowed to have weights, and (ii) in general metric spaces, the size of the coresets can depend logarithmically on the number of points. The notion of weak coresets, which have less stringent requirements than coresets, has been studied in the context of classical k-means and k-median problems. A weak coreset is a pair (J,S) of subsets of points, where S acts as a summary of the point set and J as a set of potential centers. This pair satisfies the properties that (i) S is a good summary of the data as long as the k centers are chosen from J only, and (ii) there is a good choice of k centers in J with cost close to the optimal cost. We develop this framework, which we call universal weak coresets, for constrained clustering settings. In conjunction with recent coreset constructions for constrained settings, our designs give greater data compression, are conceptually simpler, and apply to a wide range of constrained k-median and k-means problems.