We consider the problem of partitioning the nodes of a complete edge weightedgraph into (kappa) clusters so as to minimize the sum of the diameters of the clusters. Since the problem is NP-complete, our focus is on the development of good approximation algorithms. When edge weights satisfy the triangle inequality, we present the first approximation algorithm for the problem. The approximation algorithm yields a solution that has no more than 10k clusters such the total diameter of these clusters is within a factor O(log (n/(kappa))) of the optimal value fork clusters, where n is the number of nodes in the complete graph. For any fixed (kappa), we present an approximation algorithm that produces (kappa) clusters whose total diameter is at most twice the optimal value. When the distances are not required to satisfy the triangle inequality, we show that, unless P = NP, for any (rho) (ge) 1, there is no polynomial time approximation algorithm that can provide a performance guarantee of (rho) even when the number of clusters is fixed at 3. Other results obtained include a polynomial time algorithm for the problem when the underlying graph is a tree with edge weights.
展开▼
