Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics
Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics
复制标题
DOI：
10.1145/3477541
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Vincent Cohen-Addad;A. Feldmann;David Saulpic
中科院分区：
文献类型：
--
作者：
Vincent Cohen-Addad;A. Feldmann;David Saulpic
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.
