Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics
Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics
We consider the classic Facility Location, k-Median, and k-Means problems in metric spaces of constant doubling dimension. We give the first nearly linear-time approximation schemes for each problem, making a significant improvement over the state-of-the-art algorithms. Moreover, we show how to extend the techniques used to get the first efficient …