7
$\begingroup$

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.

Improve this question
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – mhum Feb 7 '13 at 0:06
  • 1
    $\begingroup$ @mhum but that doesn't say much about approximability (it does show that the problem is NP-hard) $\endgroup$ – Sasho Nikolov Feb 7 '13 at 5:56
  • 1
    $\begingroup$ @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. $\endgroup$ – Steven Feb 7 '13 at 12:17
  • $\begingroup$ 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. $\endgroup$ – Bangye Dec 25 '13 at 23:27
4
$\begingroup$

This problem is called MIN-SUM clustering and is NP-hard. There's a paper by Bartal, Charikar and Raz from 2001 that has an approximation scheme for it: the paper also includes references to the NP-hardness result and other related results.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.