# K-Clustering of a Graph maximizing intra-cluster weights?

I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.

Input: A complete graph G with non-negative integer weights on edges and an integer $K\ge 2$.

Output: A $K$-partition $P=\{P_1, ..., P_K\}$ of $V(G)$

Measure (to maximize): The sum of the weights for the edges with both endpoints in the same set of $P$, i.e.:
$$M(P)=\sum_{i=1}^k \sum_{u,v\in P_i} w\left( u,v \right)$$ where $w$ is the edge-weight function.

Thanks in advance for any suggestion.

• I'm not sure, but I think this is minimum k-cut on a complete graph? I think that maximizing the weight of intra-cluster edges should be the same as minimizing the weight of inter-cluster edges.
– mhum
Feb 7 '13 at 0:06
• @mhum but that doesn't say much about approximability (it does show that the problem is NP-hard) Feb 7 '13 at 5:56
• @mhum It is the same problem as minimum K-cut with respect to the optimal solution. This shows that the problem is NP-Hard but unfortunately an approximation algorithm for minimum K-cut isn't guaranteed to achieve the same approximation ratio on this problem. Consider for example Min Vertex-Cover and Max Independent-Set. An optimal solution for one gives an optimal solution for the other but VC is approximable within a constant while IS is not. Feb 7 '13 at 12:17
• It is also a version of the k-cluster editing or the k-correlation clustering. You may find several results in scholar google with the names as key words. Dec 25 '13 at 23:27