On Clustering to Minimize the Sum of Radii

Abstract

Let P be a set of n points in the plane. Consider the problem of finding k disks, each centered at a point in P, whose union covers P with the objective of minimizing the sum of the radii of the disks. We present an exact algorithm for this well-studied problem with polynomial running time, under the assumption that two candidate solutions can be compared efficiently. The algorithm generalizes in a straightforward manner to any fixed dimension and to some other related problems.