SIAM Journal on Computing · 1979 · 35 citations · 4 references
ComputingComputer ScienceComputer SystemsCombinatoricsComputer ArchitectureTheory Of ComputationAlgorithm AnalysisApproximation AlgorithmsCombinatorial OptimizationComputational ComplexityInteger ProgrammingBin AllocationBin PackingBin Packing ApproximationBin Packing ProblemPacking OptimizationPacking ProblemsSet Packing Problem
An $NP$-complete bin-packing problem is studied in which the objective is to maximize the number of pieces packed into a fixed set of equal capacity bins. Applications to processor and storage allocation in computer systems are discussed, and an efficient approximation algorithm is defined and studied. The main results are bounds on the complexity of the algorithm and on its performance.
4
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
Fast algorithms for bin packing
David S. Johnson · Journal of Computer and System Sciences · 1974 · 536 citations