{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreie22xkzh7oxvatmo5iwmmk7yjmizpkccw2q5lfd3q4wka4747abou",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhz22nv5rs52"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.24336v1",
  "publishedAt": "2026-03-26T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Anne Driemel",
    "Jan Höckendorff",
    "Ioannis Psarros",
    "Christian Sohler",
    "Di Yue"
  ],
  "textContent": "**Authors:** Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler, Di Yue\n\nGiven 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"
}