A Class of Simple Stochastic Online Bin Packing Algorithms

Research output: Journal contributionsJournal articlesResearchpeer-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

DOI

Recently viewed

Researchers

  1. Neele Puhlmann

Publications

  1. Hierarchical trait filtering at different spatial scales determines beetle assemblages in deadwood
  2. ActiveMath - a Learning Platform With Semantic Web Features
  3. A Playful Approach to Interactive Media in the Foreign Language Classroom
  4. Taking the pulse of Earth's tropical forests using networks of highly distributed plots
  5. Reciprocal Relationships Between Dispositional Optimism and Work Experiences
  6. A Lean Convolutional Neural Network for Vehicle Classification
  7. An analytical approach to evaluating nonmonotonic functions of fuzzy numbers
  8. NNARX networks on didactic level system identification
  9. Preventive Diagnostics for cardiovascular diseases based on probabilistic methods and description logic
  10. The model of educational reconstruction: A framework for the design of theory-based content specific interventions
  11. A cascade controller structure using an internal PID controller for a hybrid piezo-hydraulic actuator in camless internal combustion engines
  12. Computing regression statistics from grouped data
  13. The impact of explicit references in computer supported collaborative learning: Evidence from eye movement analyses
  14. Model Based Logistic Monitoring of Assembly Areas
  15. Hybrid models for future event prediction
  16. Reducing mean tardiness in a flexible job shop containing AGVs with optimized combinations of sequencing and routing rules
  17. Combined MRI-PET dissects dynamic changes in plant structures and functions
  18. Comparative study on the dehydrogenation properties of TiCl4-doped LiAlH4 using different doping techniques
  19. Excellence in Teaching and Learning
  20. Active plasma resonance spectroscopy: Eigenfunction solutions in spherical geometry
  21. Contrasting patterns of intraspecific trait variability in native and non-native plant species along an elevational gradient on Tenerife, Canary Islands
  22. Modeling Converging Material Flows In The Supply Chain
  23. A Note on Pensions and Firm Performance
  24. Some results on output algebraic feedback with applications to mechanical systems
  25. Linking large-scale and small-scale distribution patterns of steppe plant species—An example using fourth-corner analysis
  26. Logic
  27. Papers from the 10th Lancaster University Postgraduate Conference in Linguistics and Language Teaching 2015
  28. Enhancement of workability in AZ31 alloy - Processing maps