The problem of packing a set of items into a number of bins such that the total weight, volume, etc. does not exceed some maximum value. A simple algorithm (the first-fit
algorithm) takes items in the order they come and places them in the first bin in
which they fit. In 1973, J. Ullman proved that this algorithm can differ from
an optimal packing by as much at 70% (Hoffman 1998, p. 171). An alternative
strategy first orders the items from largest to smallest, then places them sequentially
in the first bin in which they fit. In 1973, D. Johnson showed that this strategy
is never suboptimal by more than 22%, and furthermore that no efficient bin-packing
algorithm can be guaranteed to do better than 22% (Hoffman 1998, p. 172).
There exist arrangements of items such that applying the packing algorithm after removing an item results in one more bin being required than the number
obtained if the item is included (Hoffman 1998, pp. 172-173). The first
such example was constructed by Sylvia Halasz and published in Graham (1976, pp. 223
and 225, Fig. 5.46).
Albers, S. and Mitzenmacher, M. "Average-Case Analyses of First Fit and Random Fit Bin Packing." Random Structures Alg.16,
240-259, 2000.Coffman, E. G. Jr.; Garey, M. R.; and Johnson,
D. S. "Approximation Algorithms for Bin-Packing--An Updated Survey."
In Algorithm
Design for Computer System Design. Vienna: Springer-Verlag, pp. 49-106,
1984.Garey, M. R.; Graham, R. L.; and Ullman, J. D. "An
Analysis of Some Packing Algorithms." In Combinatorial Algorithms. New
York: Algorithmics Press, pp. 39-47, 1973.Graham, R. L. "Bounds
on Performance of Scheduling Algorithms." In Computer
and Job-Shop Scheduling Theory (Ed. E. G. Coffman Jr.). New York:
Wiley, pp. 165-227, 1976.Johnson, D. S. "Approximation
Algorithms for Combinatorial Problems." In J. Comput. System Sci.9,
256-278, 1974.Johnson, D. S. "Approximation Algorithms for
Combinatorial Problems." In Fifth Annual ACM Symposium on Theory of Computing
(Austin, Tex., 1973). New York: Assoc. Comput. Mach., pp. 38-49,
1973.Hoffman, P. The
Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical
Truth. New York: Hyperion, 1998.
