An improved approximation algorithm for hierarchical clustering

Dasgupta and Long [7] have shown that it is possible to construct a hierarchical clustering with the guarantee that for every positive integer k, the induced k-clustering has cost at most 8 times that of the optimal k-clustering (cost of a clustering is the maximum radius of the clusters). In this paper we improve the performance ratio to 6. We also provide performance bound for the sum of the average distances in each cluster.