Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler, Di Yue · 2026
Read Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics by Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler, Di Yue (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-24336.txt.
Introduction
Driemel and co-authors give near-linear time approximation schemes for clustering in partially doubling metrics. The k-median problem picks k centers that minimize total distance to the points. Doubling metrics allow near-optimal fast schemes, but general metrics do not. The authors show the scheme extends when only one side, the points or the centers, has bounded doubling dimension. Their work gives the first such algorithm for median problems under discrete Fréchet distance. The results also extend to the facility location problem.
Catalog record
| CREATOR | Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler, Di Yue |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 279064 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.24336