A Class of Simple Stochastic Online Bin Packing Algorithms

Publikation: Beiträge in ZeitschriftenZeitschriftenaufsätzeForschungbegutachtet

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.

Titel in ÜbersetzungEine 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.
OriginalspracheEnglisch
ZeitschriftComputing
Jahrgang29
Ausgabenummer3
Seiten (von - bis)227-239
Anzahl der Seiten13
ISSN0010-485X
DOIs
PublikationsstatusErschienen - 01.09.1982
Extern publiziertJa

DOI

Zuletzt angesehen

Aktivitäten

  1. Closing Session: Summary Notes
  2. Study of digital morphing tools in the architectural design process
  3. Artificial Intelligence, Human Expertise: the Case of Provenance Linked Open Data
  4. University of Basel
  5. Working in Research-Practice-Partnerships: Empirical Findings on Motivation, Co-Construction and Learning Effects
  6. Modeling Self-Organization (3rd International Conference of the ESHS)
  7. 2nd International Conference on Advances in Data-driven Computing and Intelligent Systems (ADCIS 2023)
  8. European University Institute
  9. Mutual Learning and Knowledge Integration in Transdisciplinary Development Teams: Empirical Findings about a Collaborative Format in Teacher Education
  10. Teams are changing! Going into the wild to expand theory on dynamics in modern teamwork settings
  11. Configurating the Creation of the New: Spaces of Organising and Entrepreneuring
  12. Math Trails with an Inclusive Perspective on Students Experiences
  13. Denoising and Harmonic Detection Using Libraries of Nonorthogonal Trigonometric Bases
  14. Current Developments in Environmental Management Accounting: Towards a Comprehensive Framework for Environmental Management Accounting
  15. Minerva: A Review of Science, Learning and Policy (Fachzeitschrift)
  16. Kunstuniversität Linz
  17. Histories of Media Art (Networking) in Deep Europe in the 1990s
  18. Launching and recent developments
  19. Hypertext. Oder die Befreiung des Geistes durch die Maschine
  20. Democratic Representation by Transnational Citizens' Forums
  21. Weaving Fabrics
  22. Differential Participation and Exclusion in the Context of Current Forced Migration – Analyses in German Schools

Publikationen

  1. Analysis of a phase‐field finite element implementation for precipitation
  2. General management principles and a checklist of strategies to guide forest biodiversity conservation
  3. Does an individualized learning design improve university student online learning? A randomized field experiment
  4. Self-perceived quality of life predicts mortality risk better than a multi-biomarker panel, but the combination of both does best
  5. Deterministic Pod Repositioning in Robotic Mobile Fulfillment Systems
  6. Collaborative design prototyping in transdisciplinary research
  7. Water quantity and quality dynamics of the THC - Tuyamuyun hydroengineering complex - and implications for reservoir operation
  8. John Howard Yoder
  9. Who can nudge for sustainable development? How nudge source renders dynamic norms (in-)effective in eliciting sustainable behavior
  10. Conditions of One-Way and Two-Way Approaches in Strategic Start-Up Communication
  11. Obtaining Object Information from Stereo Vision System for Autonomous Vehicles
  12. Chip extrusion with integrated equal channel angular pressing
  13. Extending and refining the dialectic perspective on innovation: There is nothing as practical as a good theory; nothing as theoretical as a good practice
  14. A Graphic Language for Business Application Systems to Improve Communication Concerning Requirements Specification with the User
  15. Elemental analysis using electron beam‐induced K X‐rays
  16. The use of knowledge in inter-organisational knowledge-networks
  17. Race and/as Technology; or, How to do Things to Race
  18. The Balanced Scorecard and different Business Models in the textile industry
  19. “You’re Not Allowed to Give Us the Solution, but Can You Guide Us towards It?”
  20. Creating regional futures
  21. Number Pyramids as a Mathematically Rich Learning Environment for All Students
  22. 3DMIN – Challenges and Interventions in Design, Development and Dissemination of New Musical Instruments.
  23. A comparison between private and public access rules to bottlenecks - experiences and expectations from telecommunication and energy
  24. Applying standard network analysis to hypermedia systems