# Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jan 2023.

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

- [PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering](https://mlsanity.com/paper/2601.20157/) (2026)

## Abstract (arXiv)

Designing small-sized coresets, which approximately preserve the costs of the solutions for large datasets, has been an important research direction for the past decade. We consider coreset construction for a variety of general constrained clustering problems. We introduce a general class of assignment constraints, including capacity constraints on cluster centers, and assignment structure constraints for data points (modeled by a convex body B). We give coresets for clustering problems with such general assignment constraints that significantly generalize and improve known results. Notable implications include the first varepsilon-coreset for capacitated and fair k-Median with m outliers in Euclidean spaces whose size is tildeO(m + k2 varepsilon-4), generalizing and improving upon the prior bounds in [Braverman et al., FOCS' 22; Huang et al., ICLR' 23] (for capacitated k-Median, the coreset size bound obtained in [Braverman et al., FOCS' 22] is tildeO(k3 varepsilon-6), and for k-Median with m outliers, the coreset size bound obtained in [Huang et al., ICLR' 23] is tildeO(m + k3 varepsilon-5)), and the first ε-coreset of size poly(k varepsilon-1) for fault-tolerant clustering for various types of metric spaces.