Does randomization help in on-line bin packing? (Q1198004): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 03:30, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Does randomization help in on-line bin packing? |
scientific article |
Statements
Does randomization help in on-line bin packing? (English)
0 references
16 January 1993
0 references
In bin packing problems, a list of items is to be packed into a minimum number of bins of uniform size. We consider the class of on-line algorithms in which we are given the items sequentially and we must pack the current item before we see subsequent items. Lower bounds have been proved for deterministic algorithms for different bin packing problems. In this note we show that the same lower bounds hold for randomized algorithms.
0 references
analysis of algorithms
0 references
competitive analysis
0 references
bin packing
0 references
on-line algorithms
0 references
lower bounds
0 references
randomized algorithms
0 references
