Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
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. –  ShreevatsaR Jan 29 at 4:36

1 Answer 1

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.