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

CREATORAnne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler, Di Yue
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE279064
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.24336

Browse the full library · About the Tower of Babel