A Class of Simple Stochastic Online Bin Packing Algorithms

Publikation: Beiträge in ZeitschriftenZeitschriftenaufsätzeForschungbegutachtet

Standard

A Class of Simple Stochastic Online Bin Packing Algorithms. / Hoffmann, Ulrich.
in: Computing, Jahrgang 29, Nr. 3, 01.09.1982, S. 227-239.

Publikation: Beiträge in ZeitschriftenZeitschriftenaufsätzeForschungbegutachtet

Harvard

APA

Vancouver

Hoffmann U. A Class of Simple Stochastic Online Bin Packing Algorithms. Computing. 1982 Sep 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 -

DOI

Zuletzt angesehen

Publikationen

  1. On the role of linguistic features for comprehension and learning from STEM texts. A meta-analysis
  2. Elemental analysis using electron beam‐induced K X‐rays
  3. Sliding Mode Control Strategies for Maglev Systems Based on Kalman Filtering
  4. Self-perceived quality of life predicts mortality risk better than a multi-biomarker panel, but the combination of both does best
  5. Multiobjective optimal control of fluid mixing
  6. Trajectory tracking using MPC and a velocity observer for flat actuator systems in automotive applications
  7. Toward Data-Driven Analyses of Electronic Text Books
  8. Design, Modeling and Control of an Over-actuated Hexacopter Tilt-Rotor
  9. Distributable Modular Software Framework for Manufacturing Systems
  10. Confidence levels and likelihood terms in IPCC reports
  11. Determination of the construction and the material identity values of outside building components with the help of in-situ measuring procedures and FEM-simulation calculations
  12. Natural enemy diversity reduces temporal variability in wasp but not bee parasitism
  13. Microstructure and mechanical properties of as-cast Mg-Sn-Ca alloys and effect of alloying elements
  14. Continued logarithm representation of real numbers
  15. Graph-based Approaches for Analyzing Team Interaction on the Example of Soccer
  16. Principals between exploitation and exploration
  17. Geometric series with randomly increasing exponents
  18. Do Linguistic Features Influence Item Difficulty in Physics Assessments?
  19. Detection of oscillations with application in the pantograph control
  20. A dissociation between two classes of spatial abilities in elementary school children
  21. Export Boosting Policies and Firm Performance
  22. Exploring the implications of the value concept for performance assessment of sustainable business models
  23. A piezo servo hydraulic actuator for use in camless combustion engines and its control with MPC
  24. Smart Multi-coil Inductive Power Tranmission with IoT Based Visulization
  25. Light availability and land-use history drive biodiversity and functional changes in forest herb layer communities
  26. Chronic effects of a static stretching intervention program on range of motion and tissue hardness in older adults
  27. Transdisciplinary co-creation increases the utilization of knowledge from sustainable development research
  28. A Sensitive Microsystem as Biosensor for Cell Growth Monitoring and Antibiotic Testing
  29. Logistical Potentials of Load Balancing via the Build-up and Reduction of Stock
  30. Discrete Lyapunov Controllers for an Actuator in Camless Engines
  31. Control of a two-thermoelectric-cooler system for ice-clamping application using Lyapunov based approach
  32. Knowledge Graph Question Answering Datasets and Their Generalizability
  33. An intersection test for the cointegrating rank in dependent panel data
  34. Improve a 3D distance measurement accuracy in stereo vision systems using optimization methods’ approach
  35. An optimal minimum phase approximating PD regulator for robust control of a throttle plate
  36. Learner characteristics and information processing in multimedia learning
  37. Controlling a Bank Model Economy by Sliding Mode Control with Help of Kalman Filter
  38. rSOESGOPE Method Applied to Four-Tank System Modeling
  39. Spatial Tests, Familiarity with the Surroundings, and Spatial Activity Experience
  40. Passive Rotation Compensation in Parallel Kinematics Using Quaternions
  41. Performance of methods to select landscape metrics for modelling species richness
  42. The Relation of Children's Performances in Spatial Tasks at Two Different Scales of Space
  43. Modelling ammonia emissions after field application of biogas slurries
  44. Comparing marginal effects between different models and/or samples
  45. Representation of Integration Profiles Using an Ontology