Pei-Yuan Sun

Dasgupta's Hierarchical Clustering Objective: Geometry and the Price of the Cardinality Constraint

It is proved that the shifted Dasgupta optimum is exactly the minimum edge-weighted cost of a cardinality-realizable ultrametric that dominates $d_G$, which has an unavoidable linear worst case but admits substantially smaller bounds on natural sparse graph classes.