The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) <= 11/9OPT(I) + 6/9
The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) <= 11/9OPT(I) + 6/9
复制标题
DOI：
10.1007/978-3-540-74450-4_1
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
G. Dósa
中科院分区：
文献类型：
--
作者：
G. Dósa
First Fit Decreasing是一种经典的装箱算法：将项目按非递增顺序排序，然后按照此顺序将下一个项目始终打包到其适合的第一个bin中。例如，IletFFD（I）和OPT（I）分别表示算法FFD和最优算法所使用的bin的数量。本文证明了这一界是紧的.加性常数的紧界多年来一直是一个悬而未决的问题。
First Fit Decreasing is a classical bin packing algorithm: the items are ordered into their nonincreasing order, and then in this order the next item is always packed into the first bin where it fits. For an instanceIletFFD(I) andOPT(I) denote the number of the used bins by algorithm FFD, and an optimal algorithm, respectively. We show in this paper thatand that this bound is tight. The tight bound of the additive constant was an open question for many years.