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. The Role of Public Participation in Managing Uncertainty in the Implementation of the Water Framework Directive (with C. Pahl-Wostl, and K. Sigel)
  2. Mapping participation in public environmental decision-making processes: An international database on published case studies
  3. 13th IWH-CIREQ Macroeconometric Workshop: Macro-econometrics and Panel Data - IWH-CIREQ 2012
  4. Big Data, Data Trading, and Data Protection
  5. Changing learning environments at university? Comparing the learning strategies of non-traditional European students engaged in lifelong learning.
  6. How to Involve the Enduser into Quality Assurance
  7. Computer Simulation as media of knowledge production in the practice of quantum theory
  8. Blogs in the Foreign Language Classroom
  9. Workshop on Family Migration Processes in a Comparative Perspective - 2018
  10. Activist Sense and Affective Relaying in Alternative Media Practices
  11. International Symposium on Multiscale Computational Analysis of Complex Materials
  12. Lagrangian aspects of turbulent superstructures: numerical analysis of long-term dynamics and transport properties
  13. Traces of varying task formulations within the texts of students

Publications

  1. Special Issue in Acquisitional Pragmatics in Foreign Language Learning
  2. Need Satisfaction and Optimal Functioning at Leisure and Work: A Longitudinal Validation Study of the DRAMMA Model
  3. Lessons learned for spatial modelling of ecosystem services in support of ecosystem accounting
  4. The role of spatial ability in learning from instructional animations - Evidence for an ability-as-compensator hypothesis
  5. Application of feedforward artificial neural network in Muskingum flood routing
  6. Structural Synthesis of Parallel Robots with Unguided Linear Actuators
  7. Relationships between language-related variations in text tasks, reading comprehension, and students’ motivation and emotions: A systematic review
  8. From Open Access to Open Science
  9. Dynamically adjusting the k-values of the ATCS rule in a flexible flow shop scenario with reinforcement learning
  10. Intraspecific trait variation patterns along a precipitation gradient in Mongolian rangelands
  11. Interactions between ecosystem properties and land use clarify spatial strategies to optimize trade-offs between agriculture and species conservation
  12. An interdisciplinary perspective on scaling in transitions
  13. A Structure and Content Prompt-based Method for Knowledge Graph Question Answering over Scholarly Data
  14. A Theoretical Dynamical Noninteracting Model for General Manipulation Systems Using Axiomatic Geometric Structures
  15. Effect of thermo-mechanical conditions during constrained friction processing on the particle refinement of AM50 Mg-alloy phases
  16. How, when and why do negotiators use reference points?
  17. Graph-based Approaches for Analyzing Team Interaction on the Example of Soccer
  18. Dividing Apples and Pears: Towards a Taxonomy for Agile Transformation
  19. What role for frames in scalar conflicts?
  20. A Sensitive Microsystem as Biosensor for Cell Growth Monitoring and Antibiotic Testing
  21. Methods in Writing Process Research
  22. Experimental investigation of the fluid-structure interaction during deep drawing of fiber metal laminates in the in-situ hybridization process
  23. Quantum Computing and the Analog/Digital Distinction
  24. Homogenization methods for multi-phase elastic composites
  25. Acceleration of material-dominated calculations via phase-space simplicial subdivision and interpolation
  26. Erroneous examples as desirable difficulty
  27. Playing in the Spaces: Anarchism in the Classroom
  28. Student Game Design for Language Learning
  29. An analytical approach to evaluating monotonic functions of fuzzy numbers
  30. Modeling and simulation of size effects in metallic glasses with non-local continuum mechanics theory
  31. Assessing authenticity in modelling test items: deriving a theoretical model
  32. How methods influence nature's values we find – A comparison of three elicitation methods
  33. Doing space in face-to-face interaction and on interactive multimodal platforms
  34. Using Conjoint Analysis to Elicit Preferences for Occupational Health Services in Small and Microenterprises