Performance guarantees for hierarchical clustering

DOI10.1016/J.JCSS.2004.10.006MaRDI QIDQ1780451zbMATH OpenOpenAlexFDO

Authors Sanjoy Dasgupta, Philip M. Long

Publication date 13 June 2005

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2004.10.006

zbMATH Keywords

\(k\)-CenterComplete linkageHierarchical clustering

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 2089373
• Hierarchy cost of hierarchical clusterings
• Hierarchical clustering. Objective functions and algorithms
• Hierarchical clustering via spreading metrics
• Analysis of agglomerative clustering

Cites work

• A Best Possible Heuristic for the k-Center Problem
• Approximation algorithms for hierarchical location problems
• Clustering to minimize the maximum intercluster distance
• Convergence of stochastic processes
• scientific article; zbMATH DE number 1222296 (Why is no real title available?)
• scientific article; zbMATH DE number 1559578 (Why is no real title available?)
• scientific article; zbMATH DE number 1754597 (Why is no real title available?)
• Local search heuristic for k-median and facility location problems
• Nonclairvoyant scheduling
• Statistical theory in clustering
• Subquadratic approximation algorithms for clustering problems in high dimensional spaces
• The complexity of learning according to two models of a drifting environment

Cited in

(21)

• Performance analysis of hierarchical clustering algorithms
• Quantum speed-up for unsupervised learning
• Cautious active clustering
• Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints
• General bounds for incremental maximization
• Hierarchy cost of hierarchical clusterings
• Improved analysis of complete-linkage clustering
• Incremental medians via online bidding
• Clairvoyant mechanisms for online auctions
• Robust hierarchical k-center clustering
• scientific article; zbMATH DE number 2089373 (Why is no real title available?)
• Improved analysis of complete-linkage clustering
• Approximate hierarchical clustering via sparsest cut and spreading metrics
• Hierarchical clustering via spreading metrics
• Analysis of agglomerative clustering
• Hierarchical clustering better than average-linkage
• Approximation algorithms for hierarchical location problems
• The price of hierarchical clustering
• The price of hierarchical clustering
• On hierarchical diameter-clustering and the supplier problem
• An incremental version of the \(k\)-center problem on boundary of a convex polygon

This page was built for publication: Performance guarantees for hierarchical clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1780451)