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

A Class of Simple Stochastic Online Bin Packing Algorithms

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

Standard

A Class of Simple Stochastic Online Bin Packing Algorithms. / Hoffmann, Ulrich.
In: Computing, Vol. 29, No. 3, 01.09.1982, p. 227-239.

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

Harvard

Hoffmann, U 1982, 'A Class of Simple Stochastic Online Bin Packing Algorithms', Computing, vol. 29, no. 3, pp. 227-239. https://doi.org/10.1007/BF02241699

APA

Hoffmann, U. (1982). A Class of Simple Stochastic Online Bin Packing Algorithms. Computing, 29(3), 227-239. https://doi.org/10.1007/BF02241699

Vancouver

Hoffmann U. A Class of Simple Stochastic Online Bin Packing Algorithms. Computing. 1982 Sept 1;29(3):227-239. doi: 10.1007/BF02241699

Bibtex

@article{94bf60abbf5d4203a007f6a166d004d0,
title = "A Class of Simple Stochastic Online Bin Packing Algorithms",
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.",
keywords = "Informatics, AMS Subject Classifications: 68C25, approximation algorithms, Bin packing, stochastic algorithms",
author = "Ulrich Hoffmann",
year = "1982",
month = sep,
day = "1",
doi = "10.1007/BF02241699",
language = "English",
volume = "29",
pages = "227--239",
journal = "Computing",
issn = "0010-485X",
publisher = "Springer",
number = "3",

}

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 -

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

Activities

  1. Flexible Lernwege: Studium Individuale
  2. Mapping participation in public environmental decision-making processes: An international database on published case studies
  3. Re-Learning in CSCL with Learning Protocols
  4. It's Time to Talk About Time Shaping Competence: A Framework for Addressing “Time” in ESE
  5. Big Data, Data Trading, and Data Protection
  6. Presentation of the paper entitled: "Controlling a Bank Model Economy by Using an Adaptive Model Predictive Control with Help of an Extended Kalman Filter"
  7. Unboxing Uncertainties – Interrogating Forecasting and Foreclosing Future Infrastructures in the Amazon Town
  8. Answering Boolean Hybrid Questions with HAWK
  9. Dealing with temporal tensions in drug development processes
  10. BDSM Sagacity: embodying complexity
  11. Language Policy and Language Learning: New Paradigms and New Challenges - LPLL 2009
  12. Teach the teachers program
  13. Es geht um
  14. Can better texts support weak students? Interactions between text features and readers' abilities
  15. Workshop ‚Independent Local Lists – A comparative perspective’ - 2007

Publications

  1. Agency and structure in a sociotechnical transition
  2. The Forgotten Function of Forgetting
  3. Simulation based comparison of safety-stock calculation methods
  4. Need Satisfaction and Optimal Functioning at Leisure and Work: A Longitudinal Validation Study of the DRAMMA Model
  5. Implementation of a Blended-Learning Course as Part of Faculty Development
  6. Processing of CSR communication
  7. The structure of emotions in learning situations
  8. Teachers’ temporary support and worked-out examples as elements of scaffolding in mathematical modeling
  9. Taking the pulse of Earth's tropical forests using networks of highly distributed plots
  10. Lessons learned for spatial modelling of ecosystem services in support of ecosystem accounting
  11. Assessment of cognitive load in multimedia learning using dual-task methodology
  12. A New Approach for Optimal Solving Cyclic and Non-Cyclic Bus Drvier Rostering Problems
  13. Understanding Partnering Strategies in the Low-Code Platform Ecosystem
  14. Survey on challenges of Question Answering in the Semantic Web
  15. Combining linked data and statistical information retrieval
  16. Temporal processes in prime–mask interaction
  17. Robust Estimation of Linear Fixed Effects Panel Data Models with an Application to the Exporter Productivity Premium
  18. Influence of Process Parameters and Die Design on the Microstructure and Texture Development of Direct Extruded Magnesium Flat Products
  19. Relationships between language-related variations in text tasks, reading comprehension, and students’ motivation and emotions: A systematic review
  20. Dynamically adjusting the k-values of the ATCS rule in a flexible flow shop scenario with reinforcement learning
  21. Mathematical relation between extended connectivity and eigenvector coefficients.
  22. Technical concept and evaluation design of the state subsidized project [Level-Q]
  23. Systematic feature evaluation for gene name recognition
  24. Recent Advances in Intelligent Algorithms for Fault Detection and Diagnosis
  25. How generative drawing affects the learning process
  26. Control of a Three-Axis Robot with Super Twisting Sliding Mode Control
  27. From entity to process
  28. Effects of maize roots on aggregate stability and enzyme activities in soil
  29. Intraspecific trait variation patterns along a precipitation gradient in Mongolian rangelands
  30. Errors, error taxonomies, error prevention, and error management
  31. Geometric structures for the parameterization of non-interacting dynamics for multi-body mechanisms
  32. Assembly Theory for Restoring Ecosystem Structure and Functioning