the process of partitioning a set of objects into subsets (called clusters) such that each subset contains similar objects and objects in different subsets are dissimilar. There are many applications for clustering, including data compression [@pereira], analysis of gene expression data [@eisen], anomaly detection [@lee], and structuring results of search engines [@broder]. For every application, a proper objective function is used to measure the quality of a clustering. One particular objective function is the largest diameter of the clusters. If the desired number of clusters $k$ is given, we call the problem of minimizing this objective function the *diameter $k$-clustering problem*.

One of the earliest and most widely used clustering strategies is agglomerative clustering. The history of agglomerative clustering goes back at least to the 1950s (see for example [@florek; @mcquitty]). Later, biological taxonomy became one of the driving forces of cluster analysis. In [@sneath] the authors, who where the first biologists using computers to classify organisms, discuss several agglomerative clustering methods.

Agglomerative clustering is a bottom-up clustering process. At the beginning, every input object forms its own cluster. In each subsequent step, the two ’closest’ clusters will be merged until only one cluster remains. This clustering process creates a 