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

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.