agglomerative clustering algorithm using the complete linkage strategy to find a hierarchical clustering of $n$ points from ${\mathbb{R}}^d$. The running time is obviously polynomial in the description length of the input. Therefore, our only goal in this paper is to give an approximation guarantee for the diameter $k$-clustering problem. The approximation guarantee is given by a factor $\alpha$ such that the cost of the $k$-clustering computed by the algorithm is at most $\alpha$ times the cost of an optimal $k$-clustering. Although the agglomerative complete linkage clustering algorithm is widely used, there are only few theoretical results considering the quality of the clustering computed by this algorithm. It is known that there exists a certain metric distance function such that this algorithm computes a $k$-clustering with an approximation factor of $\Omega(\log k)$ [@dasgupta]. However, prior to the analysis we present in this paper, no non-trivial upper bound for the approximation guarantee of the classical complete linkage agglomerative clustering algorithm was known, and deriving such a bound has been discussed as one of the open problems in [@dasgupta].

The diameter $k$-clustering problem is closely related to the *$k$-center problem*. In this problem, we are searching for $k$ centers and the objective is 