The asymptotic worst-case behavior of the FFD heuristic for small items

CSpace

	The asymptotic worst-case behavior of the FFD heuristic for small items
	Xu, KH
	2000-11-01
发表期刊	JOURNAL OF ALGORITHMS
ISSN	0196-6774
卷号	37 期号:2 页码:237-246
摘要	The First-Fit-Decreasing (FFD) algorithm is one of the most famous and most studied methods for an approximative solution of the bin-packing problem. The question on the parametric behavior of the FFD heuristic for small items was raised in D. S. Johnson's thesis (1973, MIT, Cambridge, MA) and in E. G. Coffman et al. (1987, SLAM J. Comput. 7, 1-17): what is the asymptotic worst-case ratio for FFD when restricted to lists with item sizes in the interval (0, alpha] for alpha less than or equal to 1/2. Let R-FFD(infinity)(alpha) denote the asymptotic worst-case ratio for these lists. In his thesis, Johnson gave the values of R-FFD(infinity)(alpha) for 8/29 < < 1/4 and he conjectured that R-FFD(infinity) (1/m) = F-m = 1 + 1/m + 2 - 2/m(m + 1)(m + 2) for all integers m greater than or equal to 4. J. Csirik (1993, J. Algorithms 15, 1-28) proved that, for all integers m greater than or equal to 5, this conjecture is true when m is even. When m is odd, he further showed R-FFD(infinity)(1/m) = G(m), where G(m) = 1 + (m(2) + m - 1)/(m(m + 1)(m + 2)) = F-m + 1/(m(m + 1)(m + 2)). These results leave open the values of R-FFD(infinity)(alpha) for 0 < < 1/5 that are not the reciprocals of integers. In this paper we resolve the remaining open cases. (C) 2000 Academic Press.
语种	英语
WOS研究方向	Computer Science ; Mathematics ; Science & Technology - Other Topics
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied ; Logic
WOS记录号	WOS:000165183500001
出版者	ACADEMIC PRESS INC
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/15551
专题	中国科学院数学与系统科学研究院
通讯作者	Xu, KH
作者单位	1.Texas A&M Univ, Dept Ind Engn, College Stn, TX 77843 USA 2.Acad Sinica, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Xu, KH. The asymptotic worst-case behavior of the FFD heuristic for small items[J]. JOURNAL OF ALGORITHMS,2000,37(2):237-246.
APA	Xu, KH.(2000).The asymptotic worst-case behavior of the FFD heuristic for small items.JOURNAL OF ALGORITHMS,37(2),237-246.
MLA	Xu, KH."The asymptotic worst-case behavior of the FFD heuristic for small items".JOURNAL OF ALGORITHMS 37.2(2000):237-246.