On clustering to minimize the sum of radii

Abstract

Given a metric d defined on a set V of points (a metric space), we define the ball B(v, r) centered at u ∈ V and having radius r ≥ 0 to be the set {q ∈ V/d(v, q) ≤r}. In this work, we consider the problem of computing a minimum cost k-cover for a given set P ⊆ V of n points, where k > 0 is some given integer which is also part of the input. For k ≥ 0, a k-cover for subset Q ⊆ P is a set of at most k balls, each centered at a point in P, whose union covers (contains) Q. The cost of a set D of balls, denoted cost(D), is the sum of the radii of those balls.