Bin-Packing Problem (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
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).
See also
Cookie-Cutter Problem,Tiling Problem
Explore with Wolfram|Alpha
References
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.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Bin-Packing Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Bin-PackingProblem.html