Hierarchical Clustering: A 0.585 Revenue Approximation

Noga Alon, Yossi Azar, Danny Vainstein
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:153-162, 2020.

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
Endnote
%0 Conference Paper %T Hierarchical Clustering: A 0.585 Revenue Approximation %A Noga Alon %A Yossi Azar %A Danny Vainstein %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-alon20b %I PMLR %P 153--162 %U https://proceedings.mlr.press/v125/alon20b.html %V 125 %X 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
APA
Alon, N., Azar, Y. & Vainstein, D.. (2020). Hierarchical Clustering: A 0.585 Revenue Approximation. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:153-162 Available from https://proceedings.mlr.press/v125/alon20b.html.

Related Material