|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：Professor
性别：男
毕业院校：日本京都大学
学位：博士
所在单位：软件学院、国际信息与软件学院
学科：计算机软件与理论. 运筹学与控制论
联系方式：hanxin@dlut.edu.cn
Tight absolute bound for First Fit Decreasing bin-packing: FFD(L) <= 11/9 OPT(L)+6/9
点击次数：
论文类型：期刊论文
发表时间：2013-10-28
发表刊物：THEORETICAL COMPUTER SCIENCE
收录刊物：SCIE、EI、Scopus
卷号：510
页面范围：13-61
ISSN号：0304-3975
关键字：First Fit Decreasing; Tight bound
摘要：First Fit Decreasing is a classical bin-packing algorithm: the items are ordered by non-increasing size, and then in this order the next item is always packed into the first bin where it fits. For an instance L let FFD(L) and OPT(L) denote the number of bins used by algorithm FFD and by an optimal algorithm, respectively. In this paper we give the first complete proof of the inequality
FFD(L) <= 11/9 . OPT(L) + 6/9.
This result is best possible, as was shown earlier by Dosa (2007) [3]. The asymptotic coefficient 11/9 was proved already in 1973 by Johnson, but the tight bound of the additive constant was an open question for four decades. (C) 2013 Elsevier B.V. All rights reserved.