The diameter k-clustering problem is the problem of partitioning a finite subset of ℝ d into k subsets called clusters such that the maximum diameter of the clusters is minimized. One early clustering algorithm that computes a hierarchy of approximate solutions to this problem (for all values of k) is the agglomerative clustering algorithm with the complete linkage strategy. For decades, this algorithm has been widely used by practitioners. However, it is not well studied theoretically. In this paper, we analyze the agglomerative complete linkage clustering algorithm. Assuming that the dimension d is a constant, we show that for any k the solution computed by this algorithm is an O(logk)-approximation to the diameter k-clustering problem. Our analysis does not only hold for the Euclidean distance but for any metric that is based on a norm. Furthermore, we analyze the closely related k-center and discrete k-center problem. For the corresponding agglomerative algorithms, we deduce an approximation factor of O(logk) as well.
Furthermore, there exist provably good approximation algorithms in this case. For the discrete @math -center problem, a simple @math -approximation algorithm is known for metric spaces @cite_9 , which immediately yields a @math -approximation algorithm for the diameter @math -clustering problem. For the @math -center problem, a variety of results is known. For example, for the Euclidean metric in @cite_8 a @math -approximation algorithm with running time @math is shown. This implies a @math -approximation algorithm with the same running time for the diameter @math -clustering problem.
@cite_9 @cite_8
1973264045 2059651397
The problem of clustering a set of points so as to minimize the maximum intercluster distance is studied. An O(kn) approximation algorithm, where n is the number of points and k is the number of clusters, that guarantees solutions with an objective function value within two times the optimal solution value is presented. This approximation algorithm succeeds as long as the set of points satisfies the triangular inequality. We also show that our approximation algorithm is best possible, with respect to the approximation bound, if PZ NP. In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The surprising property of those core-sets is that their size is independent of the dimension.Using those, we present a (1+ e)-approximation algorithms for the k-center clustering and k-median clustering problems in Euclidean space. The running time of the new algorithms has linear or near linear dependency on the number of points and the dimension, and exponential dependency on 1 e and k. As such, our results are a substantial improvement over what was previously known.We also present some other clustering results including (1+ e)-approximate 1-cylinder clustering, and k-center clustering with outliers.