Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics

Vincent Cohen-Addad, Andreas Emil 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…