BinPackLab: Approximation algorithms for one-dimensional bin packing
About the Lab
The One-Dimensional Bin Packing Problem is: Given a list L containing
n weights in the range
lo,
hi, to pack the
weights into unit-capacity bins so as to minimize the total number of bins used. Bin Packing is NP-Hard.
Under the standard average-case model, each instance is a list of
n weights drawn uniformly at random from the range
lo,
hi. This
lab contains generators and code for several approximation algorithms:
- First Fit: for each weight in input order, consider the bins from left to right and pack the weight into the first (leftmost)
bin that can hold it.
- First Fit Decreasing: sort the weights in decreasing order and then apply First Fit.
Resources and Links
Code contributed by C. McGeoch and J. L. Bentley
- pack.c C
code implementing First Fit (with an internal random list generator). Uncomment
the qsort line to get First Fit Decreasing. This is tuned O(n log n) code.
- packsimplest.c
C code implementing First Fit with a slower O(n^2) implementation.
Uncomment the qsort line to get First Fit Decreasing.
Projects
- What is the asymptotic cost of First Fit?
- Characterize the cost of FF, measuring both Bin Counts and Empty
Space, as a function of l, u, and n.
- Revise the code to apply trial overloading by reporting incremental
results after every k items are packed. Does this give better views of packing
performance?