A probabilistic analysis of the Next-Fit bin packing algorithm

An infinite supply of pieces, with i.i.d. sizes, is packed under the Next-Fit packing procedure. The process A n , the number of bins required to pack n pieces, is investigated, and the first two moments are computed when the piece sizes are uniformly distributed. For this special case expressions f...

Full description

Saved in:
Bibliographic Details
Published in:Journal of algorithms 1984-01, Vol.5 (4), p.547-556
Main Author: Hofri, Micha
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An infinite supply of pieces, with i.i.d. sizes, is packed under the Next-Fit packing procedure. The process A n , the number of bins required to pack n pieces, is investigated, and the first two moments are computed when the piece sizes are uniformly distributed. For this special case expressions for the distribution of A n are also presented.
ISSN:0196-6774
1090-2678
DOI:10.1016/0196-6774(84)90007-5