Coresets for Clustering with General Assignment Constraints
| Autor: | Huang, Lingxiao, Jiang, Shaofeng H. -C., Li, Jian, Lou, Jianing, Lu, Pinyan, Wu, Xuan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: | |
| Popis: | Designing small-sized \emph{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 $\mathcal{B}$). We give coresets for constrained clustering problems with such general assignment constraints, significantly generalizing known coreset results for constrained clustering. Notable implications of our general theorem include the first $\epsilon$-coreset for capacitated and fair $k$-Median with $m$ outliers in Euclidean spaces whose size is $\tilde{O}(m + k^2 \epsilon^{-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 $\tilde{O}(k^3 \epsilon^{-6})$, and for $k$-Median with $m$ outliers, the coreset size bound obtained in [Huang et al., ICLR'23] is $\tilde{O}(m + k^3 \epsilon^{-5})$), and the first $\epsilon$-coreset of size $\mathrm{poly}(k \epsilon^{-1})$ for fault-tolerant clustering for metric spaces with bounded covering exponent. Comment: This is a merger with arXiv:2302.11151. The abstract it shortened due to the length limit of arXiv |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|