1
$\begingroup$

Consider a total of $d$ items, $\{I_1,I_2,\cdots,I_d\}$, each having a weight $w_i$ (a positive integer), and a total of $m$ bins, $\{B_1,B_2,\cdots,B_m\}$. We would like to distribute the items into the bins such that:

(1) no bin is empty;

(2) $\sum_{B_i}(|Bi|\prod_{I_j \in B_i}w_j)$ is minimized.

where $|B_i|$ is the number of items in $B_i$. Is this an NP-hard problem? If yes, how to prove it?

$\endgroup$
3
$\begingroup$

The problem is indeed NP-complete - reduce from the 3-partition problem where you are given $3n$ positive integers and asked to group them into $n$ groups such that for all the groups the sum of the elements is the same.

Note (1) that partition is strongly NP-complete - i.e remains NP-complete when the input numbers are polynomial in $n$. Note (2) that if the sum of all the groups is the same then this sum must be equal to $X$, where $X$ is the sum of all the numbers in input, divided by $n$. (3) The problem remains NP-complete even when all numbers are strictly between $X/4$ and $X/2$. In this case, each group forced to be a triple.

For each integer $a$ in the input to $3$-partition, replace it by $n^{10a}$ in the input to your problem. Use $n$ bins. Ask whether you can obtain a value of the objective function at most $3n^{10X+2}$.

For the forward direction, if there is a $3$-partition then putting each group into a bin gives value at most $n \cdot 3n \cdot n^{10X}$ for your objective function.

For the reverse direction, suppose that there is a distribution into bins such that the objective function value is at most $n \cdot 3n \cdot n^{10X}$. Make bins into groups. Note that no group adds to more than $X$, since otherwise the product in that bin would be at least $n^{10X+10}$ which is already more than objective function value. Since the input numbers all have value $X/4 < a < X/2$ it follows that all groups have size exactly $3$.

Note that this proves NP-completeness of your problem, but not strong NP-completeness. I suspect that this problem is also strongly NP-complete.

$\endgroup$
  • $\begingroup$ Bravo! Very helpful! Thanks a lot! Just a minor question: Is it sufficient to establish the hardness by asking whether we can obtain a value of the objective function at most just a specific value? Thank you in advance! $\endgroup$ – NeedHelp Oct 16 '14 at 4:07
  • $\begingroup$ Yup, see the discussion on decision problems vs optimization problems on Wikipedia, en.wikipedia.org/wiki/Decision_problem $\endgroup$ – daniello Oct 16 '14 at 7:33

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.