Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2301.08460 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910642563186688 |
|---|---|
| author | Huang, Lingxiao Li, Jian Lu, Pinyan Wu, Xuan |
| author_facet | Huang, Lingxiao Li, Jian Lu, Pinyan Wu, Xuan |
| contents | 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 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 $\tilde{O}(m + k^2 \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 $\tilde{O}(k^3 \varepsilon^{-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 \varepsilon^{-5})$), and the first $ε$-coreset of size $\mathrm{poly}(k \varepsilon^{-1})$ for fault-tolerant clustering for various types of metric spaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_08460 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds Huang, Lingxiao Li, Jian Lu, Pinyan Wu, Xuan Data Structures and Algorithms Computational Geometry 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 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 $\tilde{O}(m + k^2 \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 $\tilde{O}(k^3 \varepsilon^{-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 \varepsilon^{-5})$), and the first $ε$-coreset of size $\mathrm{poly}(k \varepsilon^{-1})$ for fault-tolerant clustering for various types of metric spaces. |
| title | Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2301.08460 |