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^{(\log(1/ \varepsilon \eps )/ \varepsilon \eps )^{O(d^2)}} n \log^4 n + 2^{O(d)} n \log^9 n, making a significant improvement over the state-of-the-art algorithm which runs in time n^{(d/ \varepsilon \eps )^{O(d)}}  .
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^{(\log(1/ \eps )/ \eps )^{O(d^2)}} n \log^4 n + 2^{O(d)} n \log^9 n, making a significant improvement over the state-of-the-art algorithms which run in time n^{(d/ \eps )^{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-Medians and k-Means, and efficient bicriteria approximation schemes for k-Medians with outliers, k-Means with outliers and k-Center .
R
nearly-linear time
nearly linear-time
D
\varepsilon
D
\varepsilon
R
algorithm which runs
algorithms which run
D
\varepsilon
A
. Moreover, we show how to extend the techniques used to get the first efficient approximation schemes for the problems of prize-collecting k-Medians and k-Means, and efficient bicriteria approximation schemes for k-Medians with outliers, k-Means with outliers and k-Center