Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation

E. G. Coffman, Joseph Y.‐T. Leung

SIAM Journal on Computing · 1979 · 35 citations · 4 references

Concepts

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.

References

4