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

Activities

  1. Teaching the machine how to assess grammar skills. Modelling verb-tense exercise characteristics as a basis for an adaptive E-learning system
  2. Performance resource depletion influence on performance: Advancing concepts and findings
  3. How to observe Culture?
  4. Mirrored piezo servo hydraulic actuators for use in camless combustion engines and its Control with mirrored inputs and MPC
  5. Chain of Fools? Sensemaking Dynamics regarding the Issue of the Blockchain Technology in the FinTech Field
  6. Swarming. Science Fact and Science Fiction of Distributed Intelligence
  7. Collaborative modeling in climatic change adaptation and energy transformation.
  8. Alterations of a visual and how they work for and at the boundaries of an interorganizational team: A multimodal exploration
  9. BDSM Sagacity: embodying complexity
  10. Performativity and Authenticity in the Web 2.0-Enhanced Foreign Language Classroom
  11. LC-MS identification of the photo-transformation products of desipramine with studying the effect of different environmental variables on the kinetics of their formation
  12. Efficacy of an Internet-based problem-solving training for teachers: Results of a randomized controlled trial.
  13. Frame-based Matrix Factorizations
  14. Presentation of the paper entitled "Design of a Real Time Path of Motion Control for Manufacturing Applications"
  15. A Tool for Applications: Wavelet Packets
  16. Digitalization and cross-border knowledge transfer: The impact on international assignments
  17. Quantitative methods for research on educating educators: Designing, conducting and analyzing control trials
  18. The link between in- and external rotation of the auditor and the quality of financial accounting and audit
  19. Acceleration and Reflection
  20. Nonlinear dynamics and opinion formation in time varying networks
  21. Information, not Representation: Crowdworker Participation on Digital Work Platforms

Publications

  1. Early Detection of Faillure in Conveyor Chain Systems by Wireless Sensor Node
  2. A reference architecture for the integration of EMIS and ERP-Systems
  3. From Knowledge to Application
  4. Metaphors and Paradigms of the Language Animal—or—The Advantage of seeing “Time Is a Resource” as a Paradigm
  5. Evaluation of standard ERP software implementation approaches in terms of their capability for business process optimization
  6. Modelling and implementation of an Order2Cash Process in distributed systems
  7. Measuring Learning Styles with Questionnaires Versus Direct Observation of Preferential Choice Behavior in Authentic Learning Situations
  8. Optimizing price levels in e-commerce applications with respect to customer lifetime values
  9. Dividing Apples and Pears: Towards a Taxonomy for Agile Transformation
  10. Developing a Complex Portrait of Content Teaching for Multilingual Learners via Nonlinear Theoretical Understandings
  11. Sharing in Christ's rule
  12. Assessment of cognitive load in multimedia learning using dual-task methodology
  13. Detection of coherent oceanic structures via transfer operators
  14. Mathematical relation between extended connectivity and eigenvector coefficients.
  15. Mining Implications From Data
  16. Executive function and Language Learning
  17. Comparing Empirical Methodologies in Pragmatics
  18. Construct- and criterion-related validity of the German Core Self-Evaluations Scale
  19. Assessing Quality of Teaching from Different Perspectives
  20. The Benefit of Web- and Computer-Based Interventions for Stress
  21. Passive Rotation of Rotational Joints and Its Computation Method
  22. Dynamic priority based dispatching of AGVs in flexible job shops
  23. In-Vehicle Sensor System for Monitoring Efficiency of Vehicle E/E Architectures
  24. Complexity and Administrative Intensity