2026-09-23T15:33:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26469 2026-09-05T19:44:24Z ddc:004 open_access

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics Driemel, Anne Höckendorff, Jan Psarros, Ioannis Sohler, Christian Yue, Di Approximation Algorithms Doubling Spaces Facility Location k-Median Discrete Fréchet Distance In the metric k-median problem we are given a finite metric space (X∪ Y, 𝐝) and the objective is to compute a set of k centers C ⊆ Y that minimizes ∑_{p ∈ X} min_{c ∈ C} 𝐝(p,c). In general metric spaces, the best polynomial time algorithm, which is due to Cohen-Addad, Grandoni, Lee, Schwiegelshohn, and Svensson [Vincent Cohen-Addad et al., 2025], computes a (2+ε)-approximation for arbitrary constant ε > 0. However, if the metric space has bounded doubling dimension, a near linear time (1+ε)-approximation algorithm is known due to the work of Cohen-Addad, Feldmann, and Saulpic [Vincent Cohen{-}Addad et al., 2021]. In this paper, 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 has bounded doubling dimension 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 has bounded doubling dimension is perhaps more natural. It 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,𝓁)-median problem under discrete Fréchet distance when 𝓁 is constant. The latter problem is a version of the k-median problem under Fréchet distance when the input consists of time series of z reals and where the centers are time series of 𝓁 reals [Anne Driemel et al., 2016]. Previously, for this problem no (1+ε)-approximation algorithm with running time polynomial in k was known. We also 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 form of 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 [Kunal Talwar, 2004] of doubling metrics to our setting. The running time of our algorithms is 2^{2^t} Õ(n+m) where t = O(ddim log ddim/ε) and where ddim is the doubling dimension of X (resp. Y). The results also extend to the metric (uncapacitated) facility location problem. We believe that our techniques are likely applicable to other problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anne Driemel and Jan Höckendorff and Ioannis Psarros and Christian Sohler and Di Yue 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.80 urn:nbn:de:0030-drops-264693 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.80 eng https://creativecommons.org/licenses/by/4.0/legalcode