to minimize the maximum distance of any input point to the nearest center. When the centers are restricted to come from the set of the input points, the problem is called the *discrete $k$-center problem*. It is known that for metric distance functions the costs of optimal solutions to all three problems are within a factor of $2$ from each other.

For the Euclidean case, we know that for fixed $k$, i.e. when we are not interested in a hierarchy of clusterings, the diameter $k$-clustering problem and the $k$-center problem are $\mathcal{NP}$-hard. In fact, it is already $\mathcal{NP}$-hard to approximate both problems with an approximation factor below $1.96$ and $1.82$ respectively [@feder].

Furthermore, there exist provably good approximation algorithms in this case. For the discrete $k$-center problem, a simple $2$-approximation algorithm is known for metric spaces [@gonzalez], which immediately yields a $4$-approximation algorithm for the diameter $k$-clustering problem. For the $k$-center problem, a variety of results is known. For example, for the Euclidean metric in [@BaHaIn02] a $(1+\epsilon)$-approximation algorithm with running time $2^{O(\nicefrac{k\log k}{\epsilon^2})}dn$ is shown. This implies a $(2+\epsilon)$-approximation algorithm with the same running time for the diameter $k$-clustering problem.

Also, for metric spaces a hierarchical clustering strategy with 