Performance guarantees for hierarchical clustering

DOI10.1016/j.jcss.2004.10.006zbMath1101.68980OpenAlexW2769245605MaRDI QIDQ1780451

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

Hierarchical clustering\(k\)-CenterComplete linkage

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items

On hierarchical diameter-clustering and the supplier problem, Improved Analysis of Complete-Linkage Clustering, Hierarchy cost of hierarchical clusterings, Improved analysis of complete-linkage clustering, An incremental version of the \(k\)-center problem on boundary of a convex polygon, Quantum speed-up for unsupervised learning, Analysis of agglomerative clustering, Incremental medians via online bidding, Cautious active clustering, Clairvoyant Mechanisms for Online Auctions, Approximation algorithms for hierarchical location problems, Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints, General bounds for incremental maximization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustering to minimize the maximum intercluster distance
• Statistical theory in clustering
• Nonclairvoyant scheduling
• The complexity of learning according to two models of a drifting environment
• A Best Possible Heuristic for the k-Center Problem
• Local search heuristic for k-median and facility location problems
• Subquadratic approximation algorithms for clustering problems in high dimensional spaces
• Convergence of stochastic processes
• Approximation algorithms for hierarchical location problems