Efficient approximation algorithms for clustering point-sets

摘要

In this paper, we consider the problem of clustering a set of n finite point-sets in ddimensional 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+n log k)-time 3-approximation algorithm and an O(km)-time (1 + 3 )-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.