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

|cite|improve this question
$\endgroup$
  • $\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 '13 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 '13 at 13:16
3
$\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$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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