Performance Guarantees for Hierarchical Clustering
Abstract
We show that for any data set in any metric space, it is possible to construct a hierarchical clustering with the guarantee that for every k , the induced k -clustering has cost at most eight times that of the optimal k -clustering. Here the cost of a clustering is taken to be the maximum radius of its clusters. Our algorithm is similar in simplicity and efficiency to common heuristics for hierarchical clustering, and we show that these heuristics have poorer approximation factors.
Cite
Text
Dasgupta. "Performance Guarantees for Hierarchical Clustering." Annual Conference on Computational Learning Theory, 2002. doi:10.1007/3-540-45435-7_24Markdown
[Dasgupta. "Performance Guarantees for Hierarchical Clustering." Annual Conference on Computational Learning Theory, 2002.](https://mlanthology.org/colt/2002/dasgupta2002colt-performance/) doi:10.1007/3-540-45435-7_24BibTeX
@inproceedings{dasgupta2002colt-performance,
title = {{Performance Guarantees for Hierarchical Clustering}},
author = {Dasgupta, Sanjoy},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2002},
pages = {351-363},
doi = {10.1007/3-540-45435-7_24},
url = {https://mlanthology.org/colt/2002/dasgupta2002colt-performance/}
}