1. //
  2. Start
  3. //
  4. Publications
  5. //
  6. A Class of Simple Stochastic Online Bin ...
  7. //

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 contributionEine 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 languageEnglish
JournalComputing
Volume29
Issue number3
Pages (from-to)227-239
Number of pages13
ISSN0010-485X
DOIs
Publication statusPublished - 01.09.1982
Externally publishedYes

    Research areas

  • Informatics
  • AMS Subject Classifications: 68C25, approximation algorithms, Bin packing, stochastic algorithms

Related by journal

Ein modifiziertes Newton-Verfahren zur Lösung des Hochrechnungsproblems nach dem Prinzip des minimalen Informationsverlustes

Merz, J., 01.03.1985, In: Computing. 35, 1, p. 51-61 11 p.

Research output: Journal contributions › Journal articles › Research › peer-review

Other publications by the same author(s)

Datenstrukturen und Algorithmen: Grundlagen, Basisalgorithmen und Lösungsstrategien für sequentielle und parallele Algorithmen

Hoffmann, U., 2013, Lüneburg: Universität Lüneburg, 403 p. (FINAL; vol. 23, no. 3).

Research output: Working paper › Working papers

Datenverarbeitungssystem 1

Hoffmann, U., 1995, Lüneburg: Universität Lüneburg, 220 p. (Final; vol. 4, no. 5).

Research output: Working paper › Working papers

Datenverarbeitungssystem 2

Hoffmann, U., 1995, Lüneburg: Universität Lüneburg, p. 221-397, 177 p. (Final; vol. 5, no. 2).

Research output: Working paper › Working papers

Einführung in die systemnahe Programmierung: Anwenderprogramme und Datenstrukturen

Hoffmann, U., 1990, Berlin: Walter de Gruyter. 371 p. (Programmierung komplexer Systeme; vol. 5)

Research output: Books and anthologies › Monographs › Education › peer-review

Grundlagen und Modelle der Programmierung

Hoffmann, U., 2013, Berlin: Lehmanns Media. 357 p. (Programmierung komplexer Systeme; vol. 2)

Research output: Books and anthologies › Monographs › Education › peer-review

DOI

Recently viewed

Publications

  1. Recognition and approach responses toward threatening objects
  2. Towards a spatial understanding of identity play
  3. Lagged Multidimensional Recurrence Quantification Analysis for Determining Leader–Follower Relationships Within Multidimensional Time Series
  4. Supporting the Development and Implementation of a Digitalization Strategy in SMEs through a Lightweight Architecture-based Method
  5. Kalman Filter for Predictive Maintenance and Anomaly Detection
  6. Volume of Imbalance Container Prediction using Kalman Filter and Long Short-Term Memory
  7. Active and semi-supervised data domain description
  8. Formative Perspectives on the Relation Between CSR Communication and CSR Practices
  9. Experimentally established correlation of friction surfacing process temperature and deposit geometry
  10. Development of a scoring parameter to characterize data quality of centroids in high-resolution mass spectra
  11. Partitioned beta diversity patterns of plants across sharp and distinct boundaries of quartz habitat islands
  12. What can conservation strategies learn from the ecosystem services approach?
  13. An Adaptive and Optimized Switching Observer for Sensorless Control of an Electromagnetic Valve Actuator in Camless Internal Combustion Engines
  14. ASSESS — automatic self-assessment using linked data
  15. Wavelet functions for rejecting spurious values
  16. Preventive Diagnostics for cardiovascular diseases based on probabilistic methods and description logic
  17. Knowledge-Enhanced Language Models Are Not Bias-Proof
  18. An analytical approach to evaluating monotonic functions of fuzzy numbers
  19. Self-regulation in error management training: emotion control and metacognition as mediators of performance effects
  20. Spaces for challenging experiences, indeterminacy, and experimentation
  21. Commitment to grand challenges in fluid forms of organizing
  22. A structural property of the wavelet packet transform method to localise incoherency of a signal
  23. Quantum Computing and the Analog/Digital Distinction
  24. A Multimethod Latent State-Trait Model for Structurally Different and Interchangeable Methods
  25. Factor structure and measurement invariance of the Students’ Self-report Checklist of Social and Learning Behaviour (SSL)
  26. Mechanism of dynamic recrystallization and evolution of texture in the hot working domains of the processing map for Mg-4Al-2Ba-2Ca Alloy
  27. A comparison of ML, WLSMV and Bayesian methods for multilevel structural equation models in small samples: A simulation study
  28. AGDISTIS - Graph-based disambiguation of named entities using linked data
  29. Species constancy depends on plot size - A problem for vegetation classification and how it can be solved
  30. A Cross-Classified CFA-MTMM Model for Structurally Different and Nonindependent Interchangeable Methods
  31. Using Conjoint Analysis to Elicit Preferences for Occupational Health Services in Small and Microenterprises
  32. Combining multiple investigative approaches to unravel functional responses to global change in the understorey of temperate forests