Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics

DOI10.1137/1.9781611974782.53zbMath1409.68328arXiv1609.09548OpenAlexW2529851164MaRDI QIDQ4575792

Vaggos Chatziafratis, Moses Charikar

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.09548

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (8)

On Dasgupta's hierarchical clustering objective and its relation to other graph parameters ⋮ Optimal hierarchical clustering on a graph ⋮ Expanding the class of global objective functions for dissimilarity-based hierarchical clustering ⋮ A two-level graph partitioning problem arising in mobile wireless communications ⋮ Unnamed Item ⋮ Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems ⋮ Ultrametric fitting by gradient descent ^*

This page was built for publication: Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics