SIAM Journal on Computing · 1986 · 222 citations · 9 references
Natural SciencesMathematicsCapacity PlanningCombinatoricsOptimizationApproximation AlgorithmsCombinatorial OptimizationBin PackingBin Packing ApproximationBin Packing ProblemPacking ProblemsWorst-case BoundsWorst-case Complexity
In the classical bin packing problem one seeks to pack a list of pieces in the minimum space using unit capacity bins. This paper addresses the more general problem in which a fixed collection of bin sizes is allowed. Three efficient approximation algorithms are described and analyzed. They guarantee asymptotic worst-case performance bounds of 2, ${3 / 2}$ and ${4 / 3}$.
9
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
D. S. Johnson, Alan Demers, Jeffrey D. Ullman et al. · SIAM Journal on Computing · 1974 · 913 citations
Orthogonal Packings in Two Dimensions
Brenda S. Baker, E. G. Coffman, Ronald L. Rivest · SIAM Journal on Computing · 1980 · 695 citations
Fast algorithms for bin packing
David S. Johnson · Journal of Computer and System Sciences · 1974 · 536 citations