A Nearly-Optimal Construction for Well-Clustered Graphs

Jul 24, 2023



This paper studies efficient algorithms for constructing hierarchical clustering (HC) with respect to Dasgupta's cost function. For any input graph G with a clear cluster-structure, our presented algorithm runs in nearly-linear time in the input size of G, and returns an O(1)-approximate (HC) tree with respect to Dasgupta's cost function; hence both the runtime and approximation ratio are optimal up to some poly-logarithmic factors. We further compare the performance of our algorithm against the previous state-of-the-art on different datasets, and report the experimental results.


Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%


Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow ICML 2023