8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – Pål GD
    Apr 8, 2013 at 11:42
  • $\begingroup$ I assume you mean Measure of efficiency - I guess what is most important is an expected run time? I will write it more formally. $\endgroup$
    – Lucas
    Apr 8, 2013 at 13:16

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.