A Class of Simple Stochastic Online Bin Packing Algorithms
Research output: Journal contributions › Journal articles › Research › peer-review
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.
| Translated title of the contribution | Eine Klasse einfacher stochastischer Online-Packungsalgorithmen: Beim eindimensionalen Packungsproblem besteht die Aufgabe darin, eine Liste vonn Eingabegrößen in möglichst wenige “Behälter” der Höhe 1 zu packen. Es wird eine Klasse von linearen Online-Algorithmen zur näherungsweisen Lösung des Packungsproblems mit Eingabegrößen, die einer bekannten Wahrscheinlichkeitsverteilung unterliegen, vorgestellt. Jeder dieser Algorithmen hängt von der Wahrscheinlichkeitsverteilung und einem Parameter ab, der die Güte des Algorithmus beeinflußt. Es wird gezeigt, daß sich der Erwartungswert der relativen Packungsdichte bei wachsender Anzahl der Eingabegrößen beliebig dicht dem Optimum nähert. |
|---|---|
| Original language | English |
| Journal | Computing |
| Volume | 29 |
| Issue number | 3 |
| Pages (from-to) | 227-239 |
| Number of pages | 13 |
| ISSN | 0010-485X |
| DOIs | |
| Publication status | Published - 01.09.1982 |
| Externally published | Yes |
- Informatics
- AMS Subject Classifications: 68C25, approximation algorithms, Bin packing, stochastic algorithms