   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 units of bin capacity.
Objective: determine the minimum number of bins needed to
accommodate all n objects.

eg. Let L = 10,   Theorem
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 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 bins.
That by either FFD or BFD uses no more than  Sushil Prasad
Thu May 13 13:03:52 EDT 1999