On Metric Clustering to Minimize the Sum of Radii

摘要

Given an n-point metric (P, d) and an integer k > 0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in n~(O(log·log△)) time and returns with high probability the optimal solution. Here, △ is the ratio between the maximum and minimum interpoint distances in the metric space. We also show that the problem is NP-hard, even in metrics induced by weighted planar graphs and in metrics of constant doubling dimension.