Efficient approximation algorithms for clustering point-sets

In this paper, we consider the problem of clustering a set of n finite point-sets in d-dimensional Euclidean space. Different from the traditional clustering problem (called points clustering problem where the to-be-clustered objects are points), the point-sets clustering problem requires that all points in a single point-set be clustered into the same cluster. This requirement disturbs the metric property of the underlying distance function among point-sets and complicates the clustering problem dramatically. In this paper, we use a number of interesting observations and techniques to overcome this difficulty. For the k-center clustering problem on point-sets, we give an O(m+nlogk)-time 3-approximation algorithm and an O(km)-time -approximation algorithm, where m is the total number of input points and k is the number of clusters. When k is a small constant, the performance ratio of our algorithm reduces to (2+ϵ) for any ϵ>0. For the k-median problem on point-sets, we present a polynomial time (3+ϵ)-approximation algorithm. Our approaches are rather general and can be easily implemented for practical purpose.