1
$\begingroup$

Is there any greedy solution with an approximation bound for the bin-packing problem when we have bins of different size?

More formally, there are $n$ bins of size $b_i$ for $i=1,\dotsc,n$, and $m$ objects, each of size $o_j$ for $j=1,\dotsc,m$.

Is there a solution that can pack all of these items into the bins?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ “Is there a solution that can pack all of these items into the bins?” is a decision problem, and I do not know what you mean by approximation for it. I think that there are several natural optimization problems related to that decision problem. $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 24, 2012 at 1:14
  • $\begingroup$ Thanks, can you refer me to any algorithm/paper that tries to solve this decision problem? $\endgroup$
    – Masood_mj
    Commented Aug 24, 2012 at 1:29
  • $\begingroup$ Um, brute force algorithm? I am not familiar with advances in exponential-time algorithms. $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 24, 2012 at 12:50

2 Answers 2

Reset to default
5
$\begingroup$

I started a project under MIT license to try to solve this problem. Currently it uses the 'best fit' approach. Sorts 'items' from largest to smallest and sorts bins from smallest to largest. Finds first bin that is large enough to use that has ALREADY been used (if possible). Let's see if we can make it a good enough solution for all.

https://github.com/asharif/packit4.me

Improve this answer
$\endgroup$
3
$\begingroup$

The first-fit algorithm is a greedy algorithm that states "For each item, it attempts to place the item in the first bin that can accommodate the item".

Improve this answer
$\endgroup$
3
  • $\begingroup$ So its 2-x approximation bound does not depend on the order of bins? Here the size of bins are different. If I use the large bins for small objects the large objects cannot be placed. $\endgroup$
    – Masood_mj
    Commented Aug 23, 2012 at 22:19
  • $\begingroup$ Since greedy is not necessarily optimal, why not place each object into the bin just large enough to fit it? It is still greedy and first fit with a slight heuristic . $\endgroup$
    – Josh C.
    Commented Aug 24, 2012 at 3:19
  • 1
    $\begingroup$ @Masood_mj I have personally implemented a first-fit packing algorithm that puts different sized objects into different sized bins. I ordered my objects from largest to smallest first and picked bins that were just larger than the object I was placing. It worked really well. $\endgroup$
    – Josh C.
    Commented Aug 24, 2012 at 15:54

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.