Dynamic bin packing with unit fraction items revisited

作者：Han, Xin^*; Peng, Chao; Ye, Deshi; Zhang, Dahai; Lan, Yan

来源：Information Processing Letters, 2010, 110(23): 1049-1054.

DOI：10.1016/j.ipl.2010.09.002

• Approximation algorithms
• Competitive ratio
• Bin packing problem

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.

• 出版日期2010-11-15
• 单位华东师范大学; 大连理工大学; 中国海洋大学; 大连东软信息学院; 浙江大学