| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427430 | Information Processing Letters | 2010 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xin Han, Chao Peng, Deshi Ye, Dahai Zhang, Yan Lan,