The minimum sum of radii (MSR) problem is that of finding the least possible sum of radii of (at most) k clusters covering a set V of n points, where the points form a graph whose edges have certain weights (distances). The minimum sum of diameters (MSD) problem is similar. The casual reader might be forgiven for assuming that MSD is trivially twice MSR, but in fact the radius of a cluster covering C, a subset of V, is defined as , that is, the radius of the smallest circle centered at one of the points of V in the cluster, and the diameter as . In particular, for a cluster covering two points, the radius is equal to the diameter. By an &agr;-approximation algorithm, we mean one that is guaranteed to produce a clustering whose sum of radii (or diameters) is at most &agr; times the optimal.
In developing this theory, much depends on the aspect ratio Δ, the ratio between the minimum (non-zero) distance in the graph and the maximum. Gibson et al. [1] produce both positive and negative complexity results, depending on Δ. In particular, they prove (Theorem 6) “the (decision version of the) problem of computing an optimal k-cover for an n-point planar metric (P,d) is NP-hard.” They observe the importance of Δ and conclude: “the existence of an exact, polynomial-time [MSR] algorithm for the metric induced by an unweighted graph has not been ruled out.” Doddi et al. [2] show, however, that unless P=NP, there is no 2-&egr;-approximation algorithm for MSD, even for unweighted graphs.
This paper goes some way to producing the polynomial-time algorithm asked for by [1]: it has (Theorem 1) a “polynomial-time exact algorithm for the unweighted MSR problem when no singletons are allowed.” Conversely, the best-known polynomial-time algorithm allowing singletons is a (3.504-&egr;)-approximation algorithm. This shows that the core of the problem is determining the singletons, an idea that I found counterintuitive until I realized that the number of singletons is ; therefore, Theorem 1 is a polynomial-time algorithm with singletons for fixed k.
There are various other results in this paper, notably (Theorem 4) a polynomial-time exact algorithm for MSD when k is constant. This is a corollary, though, of an nO(k2) algorithm, so the practical consequences may not be that great.
