AbstractWe 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.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: on-line algorithms, competitive analysis, bin packing, restricted adversaries, randomization, admission control, accommodating function
Selected references
- Baruch Awerbuch, Yair Bartal, Amos Fiat, and Adi Rosén. Competitive non-preemptive call control. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 312-320, Arlington, Virginia, 23-25 January 1994.
- Baruch Awerbuch, Rainer Gawlick, Tom Leighton, and Yuval Rabani. On-line admission control and circuit routing for high performance computing and communication. In 35th Annual Symposium on Foundations of Computer Science, pages 412-423, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
- John L. Bruno and Peter J. Downey. Probabilistic bounds for dual bin-packing. Acta Informatica, 22(3):333-345, 1985.
- E. G. Coffman, Jr. and Joseph Y-T. Leung. Combinatorial analysis of an efficient algorithm for processor and storage allocation. SIAM Journal on Computing, 8(2):202-217, May 1979.
- Edward G. Coffman, Joseph Y.-T. Leung, and D. W. Ting. Bin packing: Maximizing the number of pieces packed. Acta Informatica, 9:263-271, 1978.
- André van Vliet. An improved lower bound for on-line bin packing algorithms. Information Processing Letters, 43(5):277-284, 5 October 1992.