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. Digital, open and collaborative: New teaching formats for times of crisis – and beyond?
  2. Workshop „links4science”
  3. Effects of a seminar on mathematical modelling with MathCityMap
  4. Digitalization and Organizational Learning: Use the Double-Loop
  5. The Role of Public Participation in Managing Uncertainty in the Implementation of the Water Framework Directive (with C. Pahl-Wostl, and K. Sigel)
  6. Methods of boundary work for inter- and transdisciplinary research.
  7. Of Age Effects and the Role of Psychomotor Abilities and Practice when Using Interaction Devices
  8. Vortrag: Assessing and Managing Sustainable Business Models - A Status Update
  9. Comfort and Adaptive Cruise Control in Highly Automated Vehicles
  10. Memory Acts: Memory without Representation.: Theoretical and Methodological Suggestions
  11. 13th IWH-CIREQ Macroeconometric Workshop: Macro-econometrics and Panel Data - IWH-CIREQ 2012
  12. HyperKult IX - Computer als Medium: Augmented Space 2000
  13. Knowledge-based views on Innovation: What's in it for schools?
  14. It's Time to Talk About Time Shaping Competence: A Framework for Addressing “Time” in ESE
  15. Reflexive Multi-Criteria Evaluation as a tool to integrate Multiple Values into Decision-Making – a Case Study from Germany
  16. Metacognitive Self-Reflection and Reading Diaries
  17. Big Data, Data Trading, and Data Protection
  18. Zur Zukunft der Vergangenheit – falls es eine geben wird


Publications

  1. Special Issue in Acquisitional Pragmatics in Foreign Language Learning
  2. Database on Learning for Sustainable Development – analysis of projects
  3. Kit based motion generator for a soft walking robot
  4. The identification of up-And downstream industries using input-output tables and a firm-level application to minority shareholdings
  5. PD/PID-switching control as a human-machine interface for a semi-autonomous driver in automobiles
  6. On the Difficulty of Forgetting
  7. Need Satisfaction and Optimal Functioning at Leisure and Work: A Longitudinal Validation Study of the DRAMMA Model
  8. The structure of emotions in learning situations
  9. Assessment of cognitive load in multimedia learning using dual-task methodology
  10. Understanding Partnering Strategies in the Low-Code Platform Ecosystem
  11. Detection of coherent oceanic structures via transfer operators
  12. The role of spatial ability in learning from instructional animations - Evidence for an ability-as-compensator hypothesis
  13. Introduction: The representative turn in EU studies
  14. Soft Skills for Hard Constraints
  15. Application of feedforward artificial neural network in Muskingum flood routing
  16. Temporal processes in prime–mask interaction
  17. Diffusion patterns in small vs. large capital markets-the case of value-based management
  18. A MODEL FOR QUANTIFICATION OF SOFTWARE COMPLEXITY
  19. Challenges and boundaries in implementing social return on investment
  20. Should learners use their hands for learning? Results from an eye-tracking study
  21. Duration of Organizational Decision Processes in Organizations in View of Simulation Calculations
  22. Structural Synthesis of Parallel Robots with Unguided Linear Actuators
  23. Influence of Process Parameters and Die Design on the Microstructure and Texture Development of Direct Extruded Magnesium Flat Products
  24. Introduction Mobile Digital Practices. Situating People, Things, and Data
  25. Relationships between language-related variations in text tasks, reading comprehension, and students’ motivation and emotions: A systematic review
  26. Species composition and forest structure explain the temperature sensitivity patterns of productivity in temperate forests
  27. From Open Access to Open Science
  28. Dynamically adjusting the k-values of the ATCS rule in a flexible flow shop scenario with reinforcement learning
  29. Mathematical relation between extended connectivity and eigenvector coefficients.