Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds
Lingxiao Huang, Jian Li, Pinyan Lu, Xuan Wu · Society for Industrial and Applied Mathematics eBooks · 2025
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 ε-coreset for capacitated and fair k-MEDIAN with m outliers in Euclidean spaces whose size is Õ (m + k2ε-4), generalizing and improving upon the prior bounds in [BCJ+ 22, HJLW23] (for capacitated k-MEDIAN, the coreset size bound obtained in [BCJ+22] is Õ (k3ε-6), and for k-MEDIAN with m outliers, the coreset size bound obtained in [HJLW23] is Õ (m + k3ε-5)), and the first ε-coreset of size poly(kε-1) for fault-tolerant clustering for various types of metric spaces.