2023/01/20 by Lingxiao Huang, Jian Li, Huang, Lingxiao +4 · 2 citations
Business, Management and Accounting · Environmental Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Municipal Solid Waste Management
paper · pdf · doi:10.48550/arxiv.2301.08460
openalex publication_date 2023/01/20 · openalex created_date 2023/01/25 · openalex updated_date 2026/07/28
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 O(m + k2 ε-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 O(k3 ε-6), and for k-Median with m outliers, the coreset size bound obtained in [Huang et al., ICLR' 23] is O(m + k3 ε-5)), and the first ε-coreset of size poly(k ε-1) for fault-tolerant clustering for various types of metric spaces.