Efficient approximation algorithms for clustering point-sets (Q733558)

As is well known, cluster analysis or clustering is the assignment of a set of observations, listed as points is some space, into subsets (called clusters) so that observations in the same cluster are similar in some sense. The authors address the new problem of clustering not a set of points but a set of \(n\) finite point sets. So, the point sets clustering problem requires that all points in a single point set be clustered into the same cluster. The main problem with this kind of requirement is that the metric properties of the underlying distance function are no longer valid. Nevertheless, the authors are still able to give algorithms for the \(k\)-center clustering problem on point sets and for the \(k\)-median problem.