|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：Professor
性别：男
毕业院校：日本京都大学
学位：博士
所在单位：软件学院、国际信息与软件学院
学科：计算机软件与理论. 运筹学与控制论
联系方式：hanxin@dlut.edu.cn
扫描关注
Dynamic bin packing with unit fraction items revisited
点击次数：
论文类型：期刊论文
发表时间：2010-11-15
发表刊物：INFORMATION PROCESSING LETTERS
收录刊物：SCIE、EI、Scopus
卷号：110
期号：23
页面范围：1049-1054
ISSN号：0020-0190
关键字：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. (C) 2010 Elsevier B.V. All rights reserved.