 The Competitive Ratio for OnLine Dual Bin Packing with Restricted Input Sequences.
 Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
Nordic Journal of Computing, 8(4): 463472, 2001.
We consider the OnLine Dual Bin Packing problem where we have a fixed
number n of bins of equal size and a sequence of items.
The goal is to maximize the number of items that are packed
in the bins by an online algorithm.
An investigation of FirstFit and an algorithm called Log shows that,
in the special case where all sequences can be completely packed by an
optimal offline algorithm,
FirstFit has a constant competitive ratio, but Log does not.
In contrast, if there is no restriction on the input sequences,
Log is exponentially better than FirstFit.
This is the first separation of
this sort with a difference of more than a constant factor. We also
design randomized and deterministic algorithms for which the competitive
ratio is constant on sequences which the optimal offline algorithm can
pack using at most alpha n bins, if alpha is constant and
known to the algorithm in advance.

publication
 Link to the publication at the publisher's site  subscription may be required.
Text required by the publisher (if any):
none.

open access (150 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.