Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914421139308544 |
|---|---|
| author | Driemel, Anne Höckendorff, Jan Psarros, Ioannis Sohler, Christian Yue, Di |
| author_facet | Driemel, Anne Höckendorff, Jan Psarros, Ioannis Sohler, Christian Yue, Di |
| contents | Given a finite metric space $(X\cup Y, \mathbf{d})$ the $k$-median problem is to find a set of $k$ centers $C\subseteq Y$ that minimizes $\sum_{p\in X} \min_{c\in C} \mathbf{d}(p,c)$. In general metrics, the best polynomial time algorithm computes a $(2+ε)$-approximation for arbitrary $ε>0$ (Cohen-Addad et al. STOC 2025). However, if the metric is doubling, a near linear time $(1+ε)$-approximation algorithm is known (Cohen-Addad et al. J. ACM 2021).
We show that the $(1+ε)$-approximation algorithm can be generalized to the case when either $X$ or $Y$ has bounded doubling dimension (but the other set not). The case when $X$ is doubling is motivated by the assumption that even though $X$ is part of a high-dimensional space, it may be that it is close to a low-dimensional structure. The case when $Y$ is doubling is motivated by specific clustering problems where the centers are low-dimensional. Specifically, our work in this setting implies the first near linear time approximation algorithm for the $(k,\ell)$-median problem under discrete Fréchet distance when $\ell$ is constant. We further introduce a novel complexity reduction for time series of real values that leads to a similar result for the case of discrete Fréchet distance.
In order to solve the case when $Y$ has a bounded doubling dimension, we introduce a dimension reduction that replaces points from $X$ by sets of points in $Y$. To solve the case when $X$ has a bounded doubling dimension, we generalize Talwar's decomposition (Talwar STOC 2004) to our setting. The running time of our algorithms is $2^{2^t} \tilde O(n+m)$ where $t=O(\mathrm{ddim} \log \frac{\mathrm{ddim}}ε)$ and where $\mathrm{ddim}$ is the doubling dimension of $X$ (resp.\ $Y$). The results also extend to the metric facility location problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_24336 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics Driemel, Anne Höckendorff, Jan Psarros, Ioannis Sohler, Christian Yue, Di Data Structures and Algorithms Given a finite metric space $(X\cup Y, \mathbf{d})$ the $k$-median problem is to find a set of $k$ centers $C\subseteq Y$ that minimizes $\sum_{p\in X} \min_{c\in C} \mathbf{d}(p,c)$. In general metrics, the best polynomial time algorithm computes a $(2+ε)$-approximation for arbitrary $ε>0$ (Cohen-Addad et al. STOC 2025). However, if the metric is doubling, a near linear time $(1+ε)$-approximation algorithm is known (Cohen-Addad et al. J. ACM 2021). We show that the $(1+ε)$-approximation algorithm can be generalized to the case when either $X$ or $Y$ has bounded doubling dimension (but the other set not). The case when $X$ is doubling is motivated by the assumption that even though $X$ is part of a high-dimensional space, it may be that it is close to a low-dimensional structure. The case when $Y$ is doubling is motivated by specific clustering problems where the centers are low-dimensional. Specifically, our work in this setting implies the first near linear time approximation algorithm for the $(k,\ell)$-median problem under discrete Fréchet distance when $\ell$ is constant. We further introduce a novel complexity reduction for time series of real values that leads to a similar result for the case of discrete Fréchet distance. In order to solve the case when $Y$ has a bounded doubling dimension, we introduce a dimension reduction that replaces points from $X$ by sets of points in $Y$. To solve the case when $X$ has a bounded doubling dimension, we generalize Talwar's decomposition (Talwar STOC 2004) to our setting. The running time of our algorithms is $2^{2^t} \tilde O(n+m)$ where $t=O(\mathrm{ddim} \log \frac{\mathrm{ddim}}ε)$ and where $\mathrm{ddim}$ is the doubling dimension of $X$ (resp.\ $Y$). The results also extend to the metric facility location problem. |
| title | Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.24336 |