next up previous
Next: REFERENCES Up: NON DETERMINISTIC ALGORITHM Previous: Approximation Algorithms

Bin Packing Problem

Given: n objects to be placed in bins of capacity L each.
Object i requires tex2html_wrap_inline390 units of bin capacity.
Objective: determine the minimum number of bins needed to
accommodate all n objects.

eg. Let L = 10,

Bin packing problem is NP complete when formulated as a decision problem.
As an optimization problem bin packing is NP-hard

Approximation Algorithm for Bin Packing:

1. First Fit (FF)
- Label bins as 1, 2, 3, . . .
- Objects are considered for packing in the order 1, 2, 3, . . .
- Pack object i in bin j where j is the least index such that
bin j can contain object i.

2. Best Fit (BF)
Same as FF, except that when object i is to be packed, find out
that bin which after accommodating object i will have the least
amount of space left.

3. First Fit Decreasing (FFD)
reorder objects so that tex2html_wrap_inline392
then use FF.

4. Best Fit Decreasing (BFD)
reorder objects as above and then use BF.

Th. Packing generated by either FF or BF uses no more than tex2html_wrap_inline394 bins.
That by either FFD or BFD uses no more than tex2html_wrap_inline396


Sushil Prasad
Thu May 13 13:03:52 EDT 1999