Dynamic bin packing with unit fraction items revisited

In this paper, we will study the problem of dynamic bin packing with unit fraction items. We focus on analyzing the First Fit (FF) algorithm on this problem. There are two main results: i) we give the first bound for the FF algorithm on cases when the largest item is at most 1/k1/k; ii) we generalize the previous framework for analyzing FF and get an improved upper bound.

Research highlights
► Obtain the general bound of FF for bin packing problem with unit fraction items.
► Improve the previous upper bound of FF from 2.4942 to 2.4842.
► The analysis approach for FF is new and can be applied to other problems.