Abstract | We study geometric versions of the min-size k-clustering
problem, a clustering problem which generalizes clustering to minimize
the sum of cluster radii and has important applications. We prove that
the problem can be solved in polynomial time when the points to be clus-
tered are located on a line. For Euclidean spaces of higher dimensions,
we show that the problem is NP-hard and present polynomial time ap-
proximation schemes. The latter result yields an improved approximation
algorithm for the related problem of k-clustering to minimize the sum of
cluster diameters. |