Abstract

Clustering in metric or geometric spaces, when cast as an optimization problem, tends to be NP-hard when the number of clusters is part of the input. This is the case with the k-median and the k-center problems even in the plane. We study a variant called clustering to minimize the sum of radii: here we are given n points in a metric space, and a positive integer k, and we seek to cover the points by k balls so as to minimize the sum of the radii of the balls. In contrast to other clustering variants, we show that this problem admits a polynomial time algorithm in fixed dimensional Euclidean space. In metric spaces, we present a quasi-polynomial time algorithm if the spread of the input point set is polynomially bounded.