Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation
Authors:
- Jr. E. G. CoffmanJCJr. E. G. Coffman
- Joseph Y-T. LeungJLJoseph Y-T. Leung
- 1 May 1979
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 8 (2) , 202-217
Abstract
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.Keywords
This publication has 5 references indexed in Scilit:
- Bin packing: Maximizing the number of pieces packedActa Informatica, 1978
- An Application of Bin-Packing to Multiprocessor SchedulingSIAM Journal on Computing, 1978
- Worst-Case Performance Bounds for Simple One-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1974
- Fast algorithms for bin packingJournal of Computer and System Sciences, 1974
- Reducibility among Combinatorial Problems1972