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 graph G with negative or non-negative integer weights on edges.Output: A 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.
Max-sum graph-partition for maximizing intra-edge weights?
graph theory;graph algorithms;approximation algorithms;clustering;partition problem