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 denned as min_u∈C max_v∈C d(u, v), that is, the radius of the smallest circle centered at one of the points of V in the cluster, and the diameter as max_u,∈vC d(u, v). In particular, for a cluster covering two points, the radius is equal to the diameter. By an α-approximation algorithm, we mean one that is guaranteed to produce a clustering whose sum of radii (or diameters) is at most α times the optimal.
展开▼
