FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917593703514112 |
|---|---|
| author | Bandyapadhyay, Sayan Lochet, William Saurabh, Saket |
| author_facet | Bandyapadhyay, Sayan Lochet, William Saurabh, Saket |
| contents | Clustering with capacity constraints is a fundamental problem that attracted significant attention throughout the years. In this paper, we give the first FPT constant-factor approximation algorithm for the problem of clustering points in a general metric into $k$ clusters to minimize the sum of cluster radii, subject to non-uniform hard capacity constraints. In particular, we give a $(15+ε)$-approximation algorithm that runs in $2^{0(k^2\log k)}\cdot n^3$ time. When capacities are uniform, we obtain the following improved approximation bounds: A (4 + $ε$)-approximation with running time $2^{O(k\log(k/ε))}n^3$, which significantly improves over the FPT 28-approximation of Inamdar and Varadarajan [ESA 2020]; a (2 + $ε$)-approximation with running time $2^{O(k/ε^2 \cdot\log(k/ε))}dn^3$ and a $(1+ε)$-approximation with running time $2^{O(kd\log ((k/ε)))}n^{3}$ in the Euclidean space; and a (1 + $ε$)-approximation in the Euclidean space with running time $2^{O(k/ε^2 \cdot\log(k/ε))}dn^3$ if we are allowed to violate the capacities by (1 + $ε$)-factor. We complement this result by showing that there is no (1 + $ε$)-approximation algorithm running in time $f(k)\cdot n^{O(1)}$, if any capacity violation is not allowed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_07923 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii Bandyapadhyay, Sayan Lochet, William Saurabh, Saket Data Structures and Algorithms Computational Geometry Clustering with capacity constraints is a fundamental problem that attracted significant attention throughout the years. In this paper, we give the first FPT constant-factor approximation algorithm for the problem of clustering points in a general metric into $k$ clusters to minimize the sum of cluster radii, subject to non-uniform hard capacity constraints. In particular, we give a $(15+ε)$-approximation algorithm that runs in $2^{0(k^2\log k)}\cdot n^3$ time. When capacities are uniform, we obtain the following improved approximation bounds: A (4 + $ε$)-approximation with running time $2^{O(k\log(k/ε))}n^3$, which significantly improves over the FPT 28-approximation of Inamdar and Varadarajan [ESA 2020]; a (2 + $ε$)-approximation with running time $2^{O(k/ε^2 \cdot\log(k/ε))}dn^3$ and a $(1+ε)$-approximation with running time $2^{O(kd\log ((k/ε)))}n^{3}$ in the Euclidean space; and a (1 + $ε$)-approximation in the Euclidean space with running time $2^{O(k/ε^2 \cdot\log(k/ε))}dn^3$ if we are allowed to violate the capacities by (1 + $ε$)-factor. We complement this result by showing that there is no (1 + $ε$)-approximation algorithm running in time $f(k)\cdot n^{O(1)}$, if any capacity violation is not allowed. |
| title | FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2303.07923 |