Efficient Centroid-Linkage Clustering

MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher +4

We give an efficient algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a $c$-approximate clustering in roughly $n^{1+O(1/c^2)}$ time. We ob…