Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation

Authors:
  • JCJr. E. G. Coffman
    Jr. E. G. Coffman
  • JLJoseph Y-T. Leung
    Joseph Y-T. Leung

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.

This publication has 5 references indexed in Scilit: