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 ε-coreset for capacitated and fair k-Median with m outliers in Euclidean spaces whose size is Õ(m + k 2 ε -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 Õ(k 3 ε -6 ), and for k-Median with m outliers, the coreset size bound obtained in [HJLW23] is Õ(m + k 3 ε -5 )), and the first ε-coreset of size poly(kε -1 ) for fault-tolerant clustering for various types of metric spaces.

Our algorithm improves upon the hierarchical uniform sampling framework in [BCJ + 22, HJLW23] by employing new adaptive sampling steps, resulting in better coreset size upper bounds for (k, z)-Clustering subject to various capacity constraints. In addition, we introduce novel techniques to handle assignment structure constraints. Specifically, we relate the coreset size to a complexity measure Lip(B) of the structure constraint, where Lip(B) for convex body B is the Lipschitz constant of a certain transportation problem constrained in B, called optimal assignment transportation problem. We prove nontrivial upper bounds of Lip(B) for various polytopes, including the general matroid basis polytopes, and laminar matroid polytopes (with a better bound).