# Relaxed Bin Packing Problem

The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin.

Is there an efficient way of doing this? Is there a way that will assure there is approximately the same amount in each bin? Does having a good guess at the probability distribution of the masses help?

More explicitly:

I have $q$ objects $\{o_1...o_q\}$, each has a size $w(o_i) \in \mathbb{N}$.

I need to find a collection of $n$ disjoint bins $B = \{b_1...b_n\}$ containing the objects such that

$$\forall b_i \in B: \sum_{o \in b_i}w(o) > m$$

for some $m$. When it is possible that is.

• What is your measure? If you can put exactly (or at least) $m$ kg of stuff in each bin? Can you write the problem definition formally? Are you familiar with the Multiple Knapsack Problem (which admits a PTAS)? – Pål GD Apr 8 '13 at 11:42
• I assume you mean Measure of efficiency - I guess what is most important is an expected run time? I will write it more formally. – Lucas Apr 8 '13 at 13:16

The problem is NP-complete because it is in NP and captures the partition problem with $n = 2$ and $m = \frac12 \sum_{i = 1}^q{w(o_i)} - \frac12 \min_{i}w(o_i)$. If an equal weight partition exists, then the items can be packed in two bins each of weight $\frac12 \sum_{i = 1}^q{w(o_i)}>m$. If it doesn't, then one of the two bins would have weight at most $m$.