<p>This problem is called MIN-SUM clustering and is NP-hard. There's a <a href="http://www.cs.princeton.edu/~moses/papers/minsum.ps%E2%80%8E" rel="nofollow">paper by Bartal, Charikar and Raz</a> from 2001 that has an approximation scheme for it: the paper also includes references to the NP-hardness result and other related results. </p>

CC BY-SA 3.0
2013-12-26T01:27:10.880Z
2013-12-26T01:27:10.880Z
Suresh Venkat
<p>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.</p>

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

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

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

<p>Thanks in advance for any suggestion.</p>

CC BY-SA 3.0
2013-02-07T00:06:30.580Z
I'm not sure, but I think this is [minimum k-cut](http://en.wikipedia.org/wiki/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
CC BY-SA 3.0
2013-02-07T05:56:14.313Z
@mhum but that doesn't say much about approximability (it does show that the problem is NP-hard)
Sasho Nikolov
CC BY-SA 3.0
2013-02-07T12:17:25.657Z
@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.
Steven
CC BY-SA 3.0
2013-12-25T23:27:23.103Z
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.
Bangye
<graph-theory><graph-algorithms><approximation-algorithms><clustering><partition-problem>
K-Clustering of a Graph maximizing intra-cluster weights?
Steven
# K-Clustering of a Graph maximizing intra-cluster weights?

(Asked by: username_0 on 2013-02-06)

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.

**Tags:** graph-theory, graph-algorithms, approximation-algorithms, clustering, partition-problem
> **Comments:**
> **username_1**: I'm not sure, but I think this is [minimum k-cut](http://en.wikipedia.org/wiki/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.  
> **username_2**: @mhum but that doesn't say much about approximability (it does show that the problem is NP-hard)  
> **username_0**: @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.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2013-12-26. Score: 4 | Accepted answer

This problem is called MIN-SUM clustering and is NP-hard. There's a [paper by Bartal, Charikar and Raz](http://www.cs.princeton.edu/~moses/papers/minsum.ps%E2%80%8E) from 2001 that has an approximation scheme for it: the paper also includes references to the NP-hardness result and other related results.


---

