Back to Search
Start Over
Efficient approximation algorithms for clustering point-sets
- Source :
-
Computational Geometry . Jan2010, Vol. 43 Issue 1, p59-66. 8p. - Publication Year :
- 2010
-
Abstract
- Abstract: 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 -time 3-approximation algorithm and an -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 for any . For the k-median problem on point-sets, we present a polynomial time -approximation algorithm. Our approaches are rather general and can be easily implemented for practical purpose. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 09257721
- Volume :
- 43
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 43767611
- Full Text :
- https://doi.org/10.1016/j.comgeo.2007.12.002