<p>The problem is indeed NP-complete - reduce from the <a href="http://en.wikipedia.org/wiki/3-partition_problem" rel="nofollow">3-partition problem</a> 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. </p>

<p>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.</p>

<p>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}$.</p>

<p>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.</p>

<p>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 &lt; a &lt; X/2$ it follows that all groups have size exactly $3$.</p>

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

CC BY-SA 3.0
2014-10-16T04:07:51.483Z
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
CC BY-SA 3.0
2014-10-16T07:33:35.757Z
Yup, see the discussion on decision problems vs optimization problems on Wikipedia, http://en.wikipedia.org/wiki/Decision_problem
daniello
CC BY-SA 3.0
2014-10-15T11:37:36.530Z
2014-10-15T20:37:27.487Z
2014-10-15T20:37:27.487Z
daniello
<p>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:</p>

<p>(1) no bin is empty;</p>

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

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

<partition-problem><subset-sum>
NP-hardness of minimizing sum of weighted product
NeedHelp
# NP-hardness of minimizing sum of weighted product

(Asked by: username_0 on 2014-10-15)

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?

**Tags:** partition-problem, subset-sum

---

## 1 answers

### Answer by username_1 on 2014-10-15. Score: 3 | Accepted answer

The problem is indeed NP-complete - reduce from the [3-partition problem](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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!  
> **username_1**: Yup, see the discussion on decision problems vs optimization problems on Wikipedia, http://en.wikipedia.org/wiki/Decision_problem  

---

