A Class of Simple Stochastic Online Bin Packing Algorithms

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

Harvard

APA

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 -

DOI

Recently viewed

Researchers

  1. Mathis Brinkmann

Activities

  1. Navigating in the Digital Jungle: Articulating Combinatory Affordances of Digital Infrastructures for Collaboration
  2. A Lyapunov based PI controller with an anti-windup scheme for a purification process of potable water
  3. Developing an ontology for data science projects to facilitate the design process of a canvas
  4. On the validity of a mathematics test for the selection of university applicants for a teacher training programme
  5. Agile Portfolio Management Patterns - A Research Design
  6. Digital Transformation and Digital Business
  7. 17th Trends in Enterprise Architecture Research Workshop
  8. Benelux Conference on Artificial Intelligence 2017
  9. Implementing internet-based interventions for symptoms of depression and stress - results from a german routine care project
  10. Transparency in Research
  11. Stimmtraining - 2009
  12. Efficacy of an online- and smartphone-based Gratitude training for employees with elevated cognitive irritation - a secondary analysis of a randomized controlled trial
  13. Sub-Plenary: Partial Organization: Perspectives, Promises and Pitfalls after a Decade of Research
  14. 2023 Americas Conference on Information Systems
  15. European Conference on Information Systems 2023 (Veranstaltung)
  16. Changing ID Systems in West Africa and their Implications
  17. 12. Internationale Tagung Wirtschaftsinformatik 2015 - WI2015
  18. Undoing the ‘Migration Crisis’ Statistics. The Displacement Tracking Matrix by the International Organization for Migration and its Discontents in Niger
  19. The Sociotechnical Lives of Digital Identification: Intermediaries, Citizenship and Belonging
  20. African Migration Research Networks: Where Next?
  21. d3con - 2015
  22. A daily diary study on humor at work: Some preliminary findings
  23. Datenschutz (Organisation)
  24. Wo das Land zu Ende ist
  25. 82nd Annual Meeting of the Academy of Management - AOM 2022
  26. Video Case Studies in Online Teaching. Insights from an International Study Program
  27. Intersectionality as a lens to educational inequalities during and after the COVID-19 pandemic
  28. Die Adresse des Motivs. Oder: Das Schreiben der Ähnlichkeit
  29. Information Systems Journal (Fachzeitschrift)
  30. Wissensintegration und Wissenstransfer in der transdisziplinären Nachhaltigkeitsforschung: Das Beispiel Global TraPs.