Title:  Dynamic Bin Packing of Unit Fractions Items 
Speaker: Prudence Wong

Liverpool

Date: Tuesday,  Dec 13, 2005
Time 11-12 Venue: Room 3530, HKUST   


Abstract 
We study the dynamic bin packing problem, in which items arrive and depart
at arbitrary time.  We want to pack a sequence of unit fractions items
(i.e., items with sizes $1/w$ for some integer $w \geq 1$) into unit-size
bins such that the maximum number of bins used over all time is minimized.
Tight and almost-tight performance bounds are found for the family of
any-fit algorithms, including first-fit, best-fit, and worst-fit.  We show
that the competitive ratio of best-fit and worst-fit is $3$, which is
tight, and the competitive ratio of first-fit lies between $2.45$ and
$2.4985$. We also show that no on-line algorithm is better than
$2.428$-competitive.  This result improves the lower bound of dynamic bin
packing problem even for general items.  Ongoing research is on resource
augmentation analysis in which case the on-line algorithm is given bins
of larger size than the optimal off-line algorithm.