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?

$\endgroup$
  • 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 Aug 24 '12 at 1:14
  • $\begingroup$ Thanks, can you refer me to any algorithm/paper that tries to solve this decision problem? $\endgroup$ – Masood_mj Aug 24 '12 at 1:29
  • $\begingroup$ Um, brute force algorithm? I am not familiar with advances in exponential-time algorithms. $\endgroup$ – Tsuyoshi Ito Aug 24 '12 at 12:50
4
$\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

$\endgroup$
2
$\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".

$\endgroup$
  • $\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 Aug 23 '12 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. Aug 24 '12 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. Aug 24 '12 at 15:54

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.