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/k; ii) we generalize the previous framework for analyzing FF and get an improved upper bound. (C) 2010 Elsevier B.V. All rights reserved.
approximation algorithms competitive ratio bin packing problem