is an $O(\log k)$-approximation. Here, the $O$-notation hides a constant that is doubly exponential in $d$. This approximation guarantee holds for every level of the hierarchy computed by the algorithm. That is, we compare each computed $k$-clustering with an optimal solution for that particular value of $k$. These optimal $k$-clusterings do not necessarily form a hierarchy. In fact, there are simple examples where optimal solutions have no hierarchical structure.

Our analysis also yields that if we allow $2k$ instead of $k$ clusters and compare the cost of the computed $2k$-clustering to an optimal solution with $k$ clusters, the approximation factor is independent of $k$ and depends only on $d$. Moreover, the techniques of our analysis can be applied to prove stronger results for the $k$-center problem and the discrete $k$-center problem. For the $k$-center problem, we derive an approximation guarantee that is logarithmic in $k$ and only singly exponential in $d$. For the discrete $k$-center problem, we derive an approximation guarantee that is logarithmic in $k$ and the dependence on $d$ is only linear and additive.

Furthermore, we give almost matching upper and lower bounds for the one-dimensional case. These bounds are independent of $k$. For $d\geq2$ and the metric 