The bin-packing problem asks for a packing of 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, Austria: 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.Hoffman, P. The
Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical
Truth. New York: Hyperion, 1998.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.Johnson, D. S. "Approximation Algorithms
for Combinatorial Problems." In J. Comput. System Sci.9, 256-278,
1974.
