A Class of Simple Stochastic Online Bin Packing Algorithms

Research output: Journal contributionsJournal articlesResearchpeer-review

Authors

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.

Translated title of the contributionEine Klasse einfacher stochastischer Online-Packungsalgorithmen: Beim eindimensionalen Packungsproblem besteht die Aufgabe darin, eine Liste vonn Eingabegrößen in möglichst wenige “Behälter” der Höhe 1 zu packen. Es wird eine Klasse von linearen Online-Algorithmen zur näherungsweisen Lösung des Packungsproblems mit Eingabegrößen, die einer bekannten Wahrscheinlichkeitsverteilung unterliegen, vorgestellt. Jeder dieser Algorithmen hängt von der Wahrscheinlichkeitsverteilung und einem Parameter ab, der die Güte des Algorithmus beeinflußt. Es wird gezeigt, daß sich der Erwartungswert der relativen Packungsdichte bei wachsender Anzahl der Eingabegrößen beliebig dicht dem Optimum nähert.
Original languageEnglish
JournalComputing
Volume29
Issue number3
Pages (from-to)227-239
Number of pages13
ISSN0010-485X
DOIs
Publication statusPublished - 01.09.1982
Externally publishedYes

    Research areas

  • Informatics
  • AMS Subject Classifications: 68C25, approximation algorithms, Bin packing, stochastic algorithms

DOI

Recently viewed

Publications

  1. A Multimethod Latent State-Trait Model for Structurally Different and Interchangeable Methods
  2. An integrative research framework for enabling transformative adaptation
  3. An analytical approach to evaluating nonmonotonic functions of fuzzy numbers
  4. How can problems be turned into something good? The role of entrepreneurial learning and error mastery orientation
  5. ASSESS — automatic self-assessment using linked data
  6. The polarity field concept
  7. Value of large-scale linear networks for bird conservation
  8. Political discourse in the media
  9. Dimensions, dialectic, discourse
  10. Parameters, concepts and the terminology of outer space law: a review of the essential facilities served by outer space activities and the rules of interpretation for treaty law and soft law guidelines.
  11. NFDI4DS Shared Tasks
  12. Lernkonzepte im frühen Management
  13. The dynamics of prioritizing
  14. Methodological Challenges in Sustainability Science: A Call for Method Plurality, Procedural Rigor and Longitudinal Research
  15. An Analysis of Methane Mitigation as a Response to Climate Change
  16. Modeling of cooperative tasks in business-IT management - A proposal for a domain-specific extension of BPMN 2.0
  17. Moderators of intergroup evaluation in disadvantaged groups
  18. Arbeitsvertrag, befristeter
  19. The reception of trust in different legal systems: some lessons for Vietnam; a comparative study
  20. Determination of brand-equity from a consumer-oriented perspective
  21. Assessing Effects Through Laboratory Toxicity Testing
  22. Development and Implementation of Technical Interventions to Motivate Young Females for STEM Studies
  23. Article 3 Universal Application
  24. Response to David B. Brooks
  25. Differential responses of ecosystem components to a low-intensity fire in a Mediterranean forest
  26. Online cognitive-based intervention for depression
  27. Effects of Chronic Static Stretching on Maximal Strength and Muscle Hypertrophy
  28. Akademisches Schreiben