How to partition $n$ weighted elements into $m$ disjoint subsets such that the sum of weight of all elements in a subset is less than equals to the capacity of $j$th subset ($c_j$) . It is given that $m<n$

Example: $x_1,x_2,x_3$ are weights of 3 elements (here $n=3$). Divide these 3 elements into 2 subsets (here $m=2$) such that the $sum(X_1)<= c_1$ and $sum(X_2)<= c_2$. Here $sum(X_1)$ and $sum(X_2)$ are the summation of weights of all elements in subset 1 and 2 respectively.

The answer of the given problem is ($x_1,x_3$),($x_2$) if $x_1+x_3<=c_1$ and $x_2<=c_2$

  • $\begingroup$ I have a guess that this is NP-complete, being related to some scheduling / bin-packing problems. Oh wait actually, with $m = 2$ it's the subset-sum problem, so clearly NP-complete. $\endgroup$ – ShreevatsaR Jan 29 '14 at 4:36

This problem is NP-complete, which means that there is no algorithm that runs in time polynomial in the input size (which is the size (length) of the weights $x_i$ and $c_j$).

That this is in NP is straightforward: given a purported solution, we can easily verify whether the solution satisfies the constraint. To see that this is NP-hard as well, we can reduce the subset-sum problem to this one. Given an instance of the subset-sum problem, which is a set of integers (= weights $x_i$) and a desired sum $s$, cast it as your problem by taking $m = 2$, and the capacities to be $c_1 = s$ and $c_2 = \sum_i x_i - s$. Then, it is possible to partition the $n$ weights $x_i$ into two sets having total weight bounded by $c_1$ and $c_2$, if and only if there exists a subset of the weights $x_i$ whose sum is $s$.

That proves that it is NP-complete. However, we can, for small $n$ and $m$, write down a dynamic-programming algorithm to solve the problem. A $O(n^{m-1})$ (or so) algorithm is straightforward, but there may also exist algorithms polynomial in $m$ and $n$.


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.