Here I have a cyclic graph above. I want to partition the graph vertices into
3 clusters. (With the mindset of cluster-wise "load balancing")
Constraint: All the vertices in each cluster should be directly connected.
Goal: the deviance of the cluster-sums should be as small as possible. (In other words, the sum of loads of all clusters should be as balanced as possible.)
An infeasible example:
BF. Reason: The vertices are not directly connected within each cluster.
A feasible but bad example:
EFG. Reason: The load is not optimally balanced (Difference
59 is too large).
The optimal solution:
G. Reason: the difference among three cluster-sums (
30 respectively) is the smallest.
Which algorithm can get the optimal solution?