The Competitive Ratio for On-Line 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): 463-472, 2001.

We consider the On-Line 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 on-line algorithm. An investigation of First-Fit and an algorithm called Log shows that, in the special case where all sequences can be completely packed by an optimal off-line algorithm, First-Fit 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 First-Fit. 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 off-line 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.