# Bin packing approximation with different bin sizes

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?

• “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. Commented Aug 24, 2012 at 1:14
• Thanks, can you refer me to any algorithm/paper that tries to solve this decision problem? Commented Aug 24, 2012 at 1:29
• Um, brute force algorithm? I am not familiar with advances in exponential-time algorithms. Commented Aug 24, 2012 at 12:50

## 2 Answers

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

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

• 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. Commented Aug 23, 2012 at 22:19
• 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 . Commented Aug 24, 2012 at 3:19
• @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. Commented Aug 24, 2012 at 15:54