Approximating k-Center via Farthest-First on $δ$-Covers
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915859978518528 |
|---|---|
| author | Wilson, Jason R. |
| author_facet | Wilson, Jason R. |
| contents | The farthest-first traversal of Gonzalez is a classical $2$-approximation algorithm for solving the $k$-center problem, but its sequential nature makes it difficult to scale to very large datasets. In this work we study the effect of running farthest-first on a $δ$-cover of the dataset rather than on the full set of points. A $δ$-cover provides a compact summary of the data in which every point lies within distance $δ$ of some selected center. We prove that if farthest-first is applied to a $δ$-cover, the resulting $k$-center radius is at most twice the optimal radius plus $δ$. In our experiments on large high-dimensional datasets, we show that restricting the input to a $δ$-cover dramatically reduces the running time of the farthest-first traversal while only modestly increasing the $k$-center radius. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_13184 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Approximating k-Center via Farthest-First on $δ$-Covers Wilson, Jason R. Optimization and Control 68Q25 (Primary) 68W25 (Secondary) The farthest-first traversal of Gonzalez is a classical $2$-approximation algorithm for solving the $k$-center problem, but its sequential nature makes it difficult to scale to very large datasets. In this work we study the effect of running farthest-first on a $δ$-cover of the dataset rather than on the full set of points. A $δ$-cover provides a compact summary of the data in which every point lies within distance $δ$ of some selected center. We prove that if farthest-first is applied to a $δ$-cover, the resulting $k$-center radius is at most twice the optimal radius plus $δ$. In our experiments on large high-dimensional datasets, we show that restricting the input to a $δ$-cover dramatically reduces the running time of the farthest-first traversal while only modestly increasing the $k$-center radius. |
| title | Approximating k-Center via Farthest-First on $δ$-Covers |
| topic | Optimization and Control 68Q25 (Primary) 68W25 (Secondary) |
| url | https://arxiv.org/abs/2603.13184 |