Some unexpected expected behavior results for bin packing

Authors :: Jon Louis Bentley
Catherine C. McGeoch
L. A. McGeoch
David S. Johnson
F. T. Leighton
Source :: STOC
Publication Year :: 1984
Publisher :: ACM Press, 1984.
Abstract: We study the asymptotic expected behavior of the First Fit and First Fit Decreasing bin packing algorithms applied to items chosen uniformly from the interval (0,u], u ≤ 1. Our results indicate that the algorithms perform even better than previously expected.

Subjects :: Combinatorics
Discrete mathematics
Compact space
Bin packing problem
Interval (graph theory)
Bin
Mathematics

Database :: OpenAIRE
Journal :: Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84
Accession number :: edsair.doi...........04d06f9a721dccb3a8bfd62ae63bcc3b
Full Text :: https://doi.org/10.1145/800057.808692