Does randomization help in on-line bin packing? (Q1198004): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Multidimensional on-line bin packing: Algorithms and worst-case analysis / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parametric Lower Bound for On-Line Bin-Packing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3988808 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A lower bound for on-line bin packing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On-line bin packing in linear time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New Algorithms for Bin Packing / rank | |||
Normal rank |
Revision as of 15:35, 16 May 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