Approximating k-Center via Farthest-First on $δ$-Covers
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.13184
curl -X POST /api/v1/records/arxiv/2603.13184/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.13184/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'