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. Sino-German Summer School on Design and data analysis of biodiversity-ecosystem functioning experiments 2011
  2. Data & Drama - 2019
  3. Potentiale entdecken - Qualität sichern!
  4. Safety for everyone – studying alternative security concepts
  5. Wrapping up the Results of the 1st stage of the Biodiversity Ecosystem Functioning Experiment - BEF-China 2011
  6. The Sources of Discursive Legitimation in International Organizations
  7. On the measuring accuracy of the “Vehrs-Hebel”, a scaling apparatus for nonverbal real-time assessment of perceived quantity
  8. Strange Signs: Invented Languages from Alienation to Zany
  9. International Seminar On “Solid State Materials Processing”
  10. Development of PE pre-service teachers’ teaching performance during a long-term internship - A mixed-methods analysis of classroom videos and the written self-reflections of the PE pre-service teachers
  11. Arbeitsgemeinschaft Simulation (ASIM) Fachtagung 2017
  12. Forum on Expatriate Success
  13. Beyond Diversity: A Critical View from and on the Sociology of Culture
  14. INMATCO-Projekt: Interest in Mathematical Task Context. Von VAMPS zu INMATCO - Geschichte eines psychologisch-mathematikdidaktischen Forschungsprojekts
  15. LIT Verlag (Verlag)

Publications

  1. Evolutionary cost-tolerance optimization for complex assembly mechanisms via simulation and surrogate modeling approaches
  2. Robust Estimation of Linear Fixed Effects Panel Data Models with an Application to the Exporter Productivity Premium
  3. Duration of Organizational Decision Processes in Organizations in View of Simulation Calculations
  4. The role of task complexity, modality and aptitude in narrative task performance
  5. Complexity and Administrative Intensity
  6. Dynamic efficiency and path dependencies in venture capital markets
  7. A robust model predictive control using a feedforward structure for a hybrid hydraulic piezo actuator in camless internal combustion engines
  8. Combining an Internal SMC with an External MTPA Control Loop for an Interior PMSM
  9. Measurement and calculation of the viscosity of metals - A review of the current status and developing trends
  10. Influence of Dy in solid solution on the degradation behavior of binary Mg-Dy alloys in cell culture medium
  11. The social dynamics of knowledge hiding
  12. Self-guided internet-based and mobile-based stress management for employees
  13. On the impact of network size and average degree on the robustness of centrality measures
  14. Efficient Classification of Images with Taxonomies
  15. Is the Y/F Index Suitable for Population Genetic Studies?
  16. Quality and Adoption of COVID-19 Tracing Apps and Recommendations for Development
  17. Characterization of the microstructure evolution in IF-Steel and AA6016 during plane-strain tension and simple shear
  18. Performance analysis of a thermochemical based heat storage as an addition to cogeneration systems
  19. Empirical research on mathematical modelling
  20. Erkenntnistheorie
  21. Lung fibroblasts from patients with emphysema show markers of senescence in vitro
  22. Zur Methodologie der ‘Fehleranalyse’ in der mathematikdidaktischen Forschung
  23. Behavior of microstructure and mechanical properties in the stir zone of friction stir welded ME21 magnesium alloy
  24. Case study on delivery time determination using a machine learning approach in small batch production companies
  25. Multivariate Optimization of Analytical Methodology and a First Attempt to an Environmental Risk Assessment of β-Blockers in Hospital Wastewater
  26. The lens of polycentricity