Faster Approximation Algorithms for k-Center via Data Reduction
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912225859469312 |
|---|---|
| author | Filtser, Arnold Jiang, Shaofeng H. -C. Li, Yi Naredla, Anurag Murty Psarros, Ioannis Yang, Qiaoyuan Zhang, Qin |
| author_facet | Filtser, Arnold Jiang, Shaofeng H. -C. Li, Yi Naredla, Anurag Murty Psarros, Ioannis Yang, Qiaoyuan Zhang, Qin |
| contents | We study efficient algorithms for the Euclidean $k$-Center problem, focusing on the regime of large $k$. We take the approach of data reduction by considering $α$-coreset, which is a small subset $S$ of the dataset $P$ such that any $β$-approximation on $S$ is an $(α+ β)$-approximation on $P$. We give efficient algorithms to construct coresets whose size is $k \cdot o(n)$, which immediately speeds up existing approximation algorithms. Notably, we obtain a near-linear time $O(1)$-approximation when $k = n^c$ for any $0 < c < 1$. We validate the performance of our coresets on real-world datasets with large $k$, and we observe that the coreset speeds up the well-known Gonzalez algorithm by up to $4$ times, while still achieving similar clustering cost. Technically, one of our coreset results is based on a new efficient construction of consistent hashing with competitive parameters. This general tool may be of independent interest for algorithm design in high dimensional Euclidean spaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05888 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Approximation Algorithms for k-Center via Data Reduction Filtser, Arnold Jiang, Shaofeng H. -C. Li, Yi Naredla, Anurag Murty Psarros, Ioannis Yang, Qiaoyuan Zhang, Qin Data Structures and Algorithms We study efficient algorithms for the Euclidean $k$-Center problem, focusing on the regime of large $k$. We take the approach of data reduction by considering $α$-coreset, which is a small subset $S$ of the dataset $P$ such that any $β$-approximation on $S$ is an $(α+ β)$-approximation on $P$. We give efficient algorithms to construct coresets whose size is $k \cdot o(n)$, which immediately speeds up existing approximation algorithms. Notably, we obtain a near-linear time $O(1)$-approximation when $k = n^c$ for any $0 < c < 1$. We validate the performance of our coresets on real-world datasets with large $k$, and we observe that the coreset speeds up the well-known Gonzalez algorithm by up to $4$ times, while still achieving similar clustering cost. Technically, one of our coreset results is based on a new efficient construction of consistent hashing with competitive parameters. This general tool may be of independent interest for algorithm design in high dimensional Euclidean spaces. |
| title | Faster Approximation Algorithms for k-Center via Data Reduction |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.05888 |