2010/12/31 by Marcel R. Ackermann, Johannes Blömer, Daniel Kuntze +1 · 2 citations
Computer Science · #cs.CG #cs.DS #cs.LG
paper · pdf · doi:10.1007/s00453-012-9717-4
published as Ackermann, M. R., Blömer, J., Kuntze, D., and Sohler, C. (2014). Analysis of Agglomerative Clustering. Algorithmica, 69(1):184-215 · A preliminary version of this article appeared in Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS '11), March 2011, pp. 308-319. This article also appeared in Algorithmica. The final publication is available at http://link.springer.com/article/10.1007/s00453-012-9717-4
crossref created 2012/12/11 · crossref issued 2012/12/12 · crossref published 2012/12/12 · crossref published-online 2012/12/12 · arxiv created 2014/03/07 · arxiv updated 2014/03/10 · crossref published-print 2014/05/01 · crossref deposited 2024/05/03 · crossref indexed 2026/08/06
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(log k)-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(log k) as well.