Hierarchical Clustering: A 0.585 Revenue Approximation
Abstract
Hierarchical Clustering trees have been widely accepted as a useful form of clustering data, resulting in a prevalence of adopting fields including phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta (STOC 16’) initiated the analysis of these types of algorithms through the lenses of approximation. Later, the dual problem was considered by Moseley and Wang (NIPS 17’) dubbing it the Revenue goal function. In this problem, given a nonnegative weight $w_{ij}$ for each pair $i,j \in [n]=\{1,2, \ldots ,n\}$, the objective is to find a tree $T$ whose set of leaves is $[n]$ that maximizes the function $\sum_{i Cite this Paper BibTeX @InProceedings{pmlr-v125-alon20b, title = {Hierarchical Clustering: A 0.585 Revenue Approximation}, author = {Alon, Noga and Azar, Yossi and Vainstein, Danny}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {153--162}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/alon20b/alon20b.pdf}, url = {https://proceedings.mlr.press/v125/alon20b.html}, abstract = { Hierarchical Clustering trees have been widely accepted as a useful form of clustering data, resulting in a prevalence of adopting fields including phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta (STOC 16’) initiated the analysis of these types of algorithms through the lenses of approximation. Later, the dual problem was considered by Moseley and Wang (NIPS 17’) dubbing it the Revenue goal function. In this problem, given a nonnegative weight $w_{ij}$ for each pair $i,j \in [n]=\{1,2, \ldots ,n\}$, the objective is to find a tree $T$ whose set of leaves is $[n]$ that maximizes the function $\sum_{i Copy to Clipboard Download Endnote %0 Conference Paper %T Hierarchical Clustering: A 0.585 Revenue Approximation %A Noga Alon %A Yossi Azar %A Dann