Hierarchy cost of hierarchical clusterings

The hierarchy cost of a hierarchical clustering measures the quality of the induced k-clusterings compared to optimal k-clusterings. It is defined as the maximal ratio of the cost of an induced k-clustering with respect to k-center to the cost of an optimal k-clustering as k ranges over all possible values. In this article it is shown that there is always an hierarchical clustering with hierarchy cost of at most $$1.25+0.25\sqrt{41} \approx 2.85$$ 1.25 + 0.25 41 ≈ 2.85 in the one dimensional case. Moreover, there is a hierarchical clustering with hierarchy cost of at most $$3+2\sqrt{2} \approx 5.83$$ 3 + 2 2 ≈ 5.83 in general metric spaces.