Approximation Algorithms for Min-Sum P-Clustering

We consider the following problem: Given a graph with edge lengths satisfying the triangle inequality, partition its node set into p subsets, minimizing the total length of edges whose two ends are in the same subset. For this problem we present an approximation algorithm which comes to at most twice the optimal value. For clustering into two equal-sized sets, the exact bound on the maximum possible error ratio of our algorithm is between 1.686 and 1.7. 1 Introduction Let G = (V; E) be a given complete undirected graph, with node set V and edge set E. The edges in E have lengths that satisfy the triangle inequality. The min-sum p-clustering problem requires to partition V into p subsets, possibly of given sizes, minimizing the total length of edges whose two ends are in the same subset. The problem has numerous applications in various areas (see, for example, [2, 3, 4, 5]). In this paper we derive an approximation algorithm for a version of the problem in which the sizes of the clust..