Linear time-approximation algorithms for bin packing

被引：21

作者：

Zhang, GC

Cai, XQ

Wong, CK ^{[1
]}

机构：

[1] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Shatin, Hong Kong, Peoples R China

[2] Chinese Univ Hong Kong, Dept Syst Engn & Engn Management, Shatin, Hong Kong, Peoples R China

[3] Zhejiang Univ, Dept Math, Hangzhou 310027, Peoples R China

来源：

OPERATIONS RESEARCH LETTERS | 2000年 / 26卷 / 05期

关键词：

bin packing; absolute worst-case ratio; linear time algorithm;

D O I：

10.1016/S0167-6377(99)00077-2

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Simchi-Levi (Naval Res. Logist. 41 (1994) 579-585) proved that the famous bin packing algorithms FF and BF have an absolute worst-case ratio of no more than 7/4, and FFD and BFD have an absolute worst-case ratio of 3/2, respectively. These algorithms run in time O(n log n). In this paper, we provide a linear time constant space (number of bins kept during the execution of the algorithm is constant) off-line approximation algorithms with absolute worst-case ratio 3/2. This result is best possible unless P = NP. Furthermore, we present a linear time constant space on-line algorithm and prove that the absolute worst-case ratio is 7/4. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：217 / 222

页数：6