A Class of Simple Stochastic Online Bin Packing Algorithms

Publikation: Beiträge in ZeitschriftenZeitschriftenaufsätzeForschungbegutachtet

Authors

In the one-dimensional bin packing problem a list of n items has to be packed into a minimum number of unit-capacity bins. A class of linear online algorithms for the approximate solution of bin packing with items drawn from a known probability distribution is presented. Each algorithm depends on the distribution and on a parameter controlling the performance of the algorithm. It is shown that with increasing number of items the expected performance ratio has an arbitrary small deviation from optimum. © 1982 Springer-Verlag.
Titel in ÜbersetzungEine Klasse einfacher stochastischer Online-Packungsalgorithmen
OriginalspracheEnglisch
ZeitschriftComputing
Jahrgang29
Ausgabenummer3
Seiten (von - bis)227-239
Anzahl der Seiten13
ISSN0010-485X
DOIs
PublikationsstatusErschienen - 09.1982
Extern publiziertJa

DOI