Variable Sized Bin Packing

Donald K. Friesen, Michael A. Langston

SIAM Journal on Computing · 1986 · 222 citations · 9 references

Concepts

Abstract

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}$.

References

9