An O(n) bin-packing algorithm for uniformly distributed data (Q1065544)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An O(n) bin-packing algorithm for uniformly distributed data |
scientific article; zbMATH DE number 3924125
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An O(n) bin-packing algorithm for uniformly distributed data |
scientific article; zbMATH DE number 3924125 |
Statements
An O(n) bin-packing algorithm for uniformly distributed data (English)
0 references
1986
0 references
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})\).
0 references
heuristic algorithm
0 references
probabilistic analysis
0 references
on-line algorithm
0 references
bin- packing problem
0 references
