# NP-hardness of minimizing sum of weighted product

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?

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.

• 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! – NeedHelp Oct 16 '14 at 4:07
• Yup, see the discussion on decision problems vs optimization problems on Wikipedia, en.wikipedia.org/wiki/Decision_problem – daniello Oct 16 '14 at 7:33