Average-case analyses of first fit and random fit bin packing

Susanne Albers, Michael Mitzenmacher

Abstract

We prove that the First Fit bin packing algorithm is stable under the input distribution U{k−2, k} for all k≥3, settling an open question from the recent survey by Coffman, Garey, and Johnson [“Appro...
BibTeX
@inproceedings{albers1998average,
  author = {Susanne Albers and Michael Mitzenmacher},
  title = {{Average-case analyses of first fit and random fit bin packing}},
  booktitle = {SODA},
  year = {1998},
}

Loading related content...

Figure