Near-linear Time Approximation Schemes for Clustering in Doubling Metrics - Sorbonne Université
Journal Articles Journal of the ACM (JACM) Year : 2021

Near-linear Time Approximation Schemes for Clustering in Doubling Metrics

Abstract

We consider the classic Facility Location, k -Median, and k -Means problems in metric spaces of doubling dimension d . We give nearly linear-time approximation schemes for each problem. The complexity of our algorithms is Õ(2 (1/ε) O(d2) n) , making a significant improvement over the state-of-the-art algorithms that run in time n (d/ε) O(d) . Moreover, we show how to extend the techniques used to get the first efficient approximation schemes for the problems of prize-collecting k -Median and k -Means and efficient bicriteria approximation schemes for k -Median with outliers, k -Means with outliers and k -Center.

Dates and versions

hal-03944554 , version 1 (18-01-2023)

Identifiers

Cite

Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic. Near-linear Time Approximation Schemes for Clustering in Doubling Metrics. Journal of the ACM (JACM), 2021, 68 (6), pp.1-34. ⟨10.1145/3477541⟩. ⟨hal-03944554⟩
39 View
0 Download

Altmetric

Share

More