The diameter k-clustering problem is the problem of partitioning a finite subset of ℝ d into k subsets called clusters such that the maximum diameter of the clusters is minimized. One early clustering algorithm that computes a hierarchy of approximate solutions to this problem (for all values of k) is the agglomerative clustering algorithm with the complete linkage strategy. For decades, this algorithm has been widely used by practitioners. However, it is not well studied theoretically. In this paper, we analyze the agglomerative complete linkage clustering algorithm. Assuming that the dimension d is a constant, we show that for any k the solution computed by this algorithm is an O(logk)-approximation to the diameter k-clustering problem. Our analysis does not only hold for the Euclidean distance but for any metric that is based on a norm. Furthermore, we analyze the closely related k-center and discrete k-center problem. For the corresponding agglomerative algorithms, we deduce an approximation factor of O(logk) as well.
Furthermore, there exist provably good approximation algorithms in this case. For the discrete @math -center problem, a simple @math -approximation algorithm is known for metric spaces @cite_9 , which immediately yields a @math -approximation algorithm for the diameter @math -clustering problem. For the @math -center problem, a variety of results is known. For example, for the Euclidean metric in @cite_8 a @math -approximation algorithm with running time @math is shown. This implies a @math -approximation algorithm with the same running time for the diameter @math -clustering problem.
@cite_9 @cite_8
2162317280 1994698869 1999939497 2950999367
For a set Pof npoints in i¾?2, the Euclidean 2-center problem computes a pair of congruent disks of the minimal radius that cover P. We extend this to the (2,k)-center problem where we compute the minimal radius pair of congruent disks to cover ni¾? kpoints of P. We present a randomized algorithm with O(nk7log3n) expected running time for the (2,k)-center problem. We also study the (p,k)-center problem in i¾?2under the i¾? i¾? -metric. We give solutions for p= 4 in O(kO(1)nlogn) time and for p= 5 in O(kO(1)nlog5n) time. The min-sum k-clustering problem in a metric space is to find a partition of the space into k clusters as to minimize the total sum of distances between pairs of points assigned to the same cluster. We give the first polynomial time non-trivial approximation algorithm for this problem. The algorithm provides an @math approximation to the min-sum k -clustering problem in general metric spaces, with running time @math . The result is based on embedding of metric spaces into hierarchically separated trees. We also provide a bicriteria approximation result that provides a constant approximation factor solution with only a constant factor increase in the number of clusters. This result is obtained by modifying and drawing ideas from recently developed primal dual approximation algorithms for facility location. In this paper we present an n^ O(k1-1 d) -time algorithm for solving the k -center problem in , under Lźfty - and L2 -metrics. The algorithm extends to other metrics, and to the discrete k -center problem. We also describe a simple (1+ź) -approximation algorithm for the k -center problem, with running time O(nlog k) + (k ź)^ O(k1-1 d) . Finally, we present an n^ O(k1-1 d) -time algorithm for solving the L -capacitated k -center problem, provided that L=Ω(n k1-1 d) or L=O(1) . This paper presents a distributed O(1)-approximation algorithm, with expected- @math running time, in the @math model for the metric facility location problem on a size- @math clique network. Though metric facility location has been considered by a number of researchers in low-diameter settings, this is the first sub-logarithmic-round algorithm for the problem that yields an O(1)-approximation in the setting of non-uniform facility opening costs. In order to obtain this result, our paper makes three main technical contributions. First, we show a new lower bound for metric facility location, extending the lower bound of B a (ICALP 2005) that applies only to the special case of uniform facility opening costs. Next, we demonstrate a reduction of the distributed metric facility location problem to the problem of computing an O(1)-ruling set of an appropriate spanning subgraph. Finally, we present a sub-logarithmic-round (in expectation) algorithm for computing a 2-ruling set in a spanning subgraph of a clique. Our algorithm accomplishes this by using a combination of randomized and deterministic sparsification.