enter image description here

In brief:
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: ADG CE BF. Reason: The vertices are not directly connected within each cluster.
A feasible but bad example: AB CD EFG. Reason: The load is not optimally balanced (Difference 14 14 59 is too large).
The optimal solution: ABCD EF G. Reason: the difference among three cluster-sums (28 29 30 respectively) is the smallest.

Which algorithm can get the optimal solution?


Your problem is $\text{NP}$-hard. To see why, consider the version of the 3-Partition problem where we're given multiset $ X = \{ x_1, x_2, \ldots, x_{3n}\}$ of $3n$ nonnegative integers, and we need to decide whether $X$ can be partitioned into three disjoint multisets with the same sum each. Clearly, an instance $X = \{ x_1, x_2, \ldots, x_{3n}\}$ of the 3-Partition problem can be translated in polynomial time into a complete graph $G = \langle V, E \rangle$, where $V = \{ v_i\}_{i\in [3n]}$ and for each $v_i$, we have that the weight $w(v_i) = x_i$. That is, we view the integers as $3n$ vertices, and every two vertices are connected with an edge. Obviously, a balanced 3-clustering of $G$ corresponds to an appropriate 3-partition of the multiset $X$.


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.