A Class of Simple Stochastic Online Bin Packing Algorithms
Research output: Journal contributions › Journal articles › Research › peer-review
Standard
In: Computing, Vol. 29, No. 3, 01.09.1982, p. 227-239.
Research output: Journal contributions › Journal articles › Research › peer-review
Harvard
APA
Vancouver
Bibtex
}
RIS
TY - JOUR
T1 - A Class of Simple Stochastic Online Bin Packing Algorithms
AU - Hoffmann, Ulrich
PY - 1982/9/1
Y1 - 1982/9/1
N2 - 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.
AB - 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.
KW - Informatics
KW - AMS Subject Classifications: 68C25
KW - approximation algorithms
KW - Bin packing
KW - stochastic algorithms
UR - http://www.scopus.com/inward/record.url?scp=0020280013&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/b374faad-ba37-35d2-b45b-97e540d7b078/
U2 - 10.1007/BF02241699
DO - 10.1007/BF02241699
M3 - Journal articles
VL - 29
SP - 227
EP - 239
JO - Computing
JF - Computing
SN - 0010-485X
IS - 3
ER -