Minimizing sum of products

Question

Consider a total of $d$ items, $\{I_1, I_2, \cdots, I_d \}$, each having a weight $w_i$, 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}(\prod_{I_j \in B_i}w_j)$ is minimized.

Is this an NP problem?

Answer 1

Finally, we believe the above problem can be reduced from the multiprocessor scheduling problem. Several key points in establishing the proof:

1. Minimizing $\sum_{B_i}(\prod_{I_j\in B_i}{w_j})$ is equivalent to minimizing $\max\prod_{I_j\in B_i}{w_j}$ (according to the AM–GM inequality)

2. Replace the numbers in multiprocessor scheduling by their logarithms.

Answer 2

It is a NP-hard problem. It can be reduced from 3 dimensional matching problem.