An O(n) bin-packing algorithm for uniformly distributed data
From MaRDI portal
We introduce a new on-line algorithm for the classical bin-packing problem. The algorithm opens a bounded number of empty bins at a time. Supposing that the sizes of the elements are uniformly distributed on the interval (0,1], we can decide the number of simultaneously opened bins. We analyse this algorithm from probabilistic point of view. Our main result is that the expected waste of this algorithm is \(O(n^{2/3})\).
Recommendations
- scientific article; zbMATH DE number 1870507
- On the sum-of-squares algorithm for bin packing
- The average-case analysis of some on-line algorithms for bin packing
- On-Line Bin Packing of Items of Random Sizes, II
- Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings
Cites work
- Bin packing as a random walk: A note on Knödel's paper
- scientific article; zbMATH DE number 3722129 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Probabilistic analysis for simple one- and two-dimensional bin packing algorithms
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
Cited in
(8)- The average-case analysis of some on-line algorithms for bin packing
- Bin packing using semi-ordinal data
- On the sum-of-squares algorithm for bin packing
- On the Sum-of-Squares algorithm for bin packing
- scientific article; zbMATH DE number 62475 (Why is no real title available?)
- On-Line Bin Packing of Items of Random Sizes, II
- scientific article; zbMATH DE number 1870507 (Why is no real title available?)
- Interior-point-based online stochastic bin packing
This page was built for publication: An O(n) bin-packing algorithm for uniformly distributed data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1065544)
