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).