Abstract
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.
| Titel in Übersetzung | 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. |
|---|---|
| Originalsprache | Englisch |
| Zeitschrift | Computing |
| Jahrgang | 29 |
| Ausgabenummer | 3 |
| Seiten (von - bis) | 227-239 |
| Seitenumfang | 13 |
| ISSN | 0010-485X |
| DOIs | |
| Publikationsstatus | Erschienen - 01.09.1982 |
| Extern publiziert | Ja |
Fachgebiete und Schlagwörter
- Informatik
ASJC Scopus Sachgebiete
- Numerische Mathematik
- Software.
- Theoretische Informatik und Mathematik
- Theoretische Informatik
- Angewandte Informatik
- Computational Mathematics
Fingerprint
Untersuchen Sie die Forschungsthemen von „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.“. Zusammen bilden sie einen einzigartigen Fingerprint.Dieses zitieren
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver