(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science

Fair versus Unrestricted Bin Packing
Yossi Azar, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen
Algorithmica, 34(2): 181-196, 2002

We consider the on-line Dual Bin Packing problem where we have n unit size bins 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.
We investigate unrestricted algorithms that have the power of performing admission control on the items, i.e., rejecting items while there is enough space to pack them, versus fair algorithms that reject an item only when there is not enough space to pack it.
We show that by performing admission control on the items, we get better performance compared with the performance achieved on the fair version of the problem. Our main result shows that with an unfair variant of First-Fit, we can pack approximately 2/3 of the items for sequences for which an optimal off-line algorithm can pack all the items.
This is in contrast to standard First-Fit where we show an asymptotically tight hardness result: if the number of bins can be chosen arbitrarily large, the fraction of the items packed by First-Fit comes arbitrarily close to 5/8.

The publication is available at www.springerlink.com (subscription may be required).