Linear time-approximation algorithms for bin packing
Publication in refereed journal


引用次數
替代計量分析
.

其它資訊
摘要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.
著者Zhang GC, Cai XQ, Wong CK
期刊名稱Operations Research Letters
出版年份2000
月份6
日期1
卷號26
期次5
出版社ELSEVIER SCIENCE BV
頁次217 - 222
國際標準期刊號0167-6377
電子國際標準期刊號1872-7468
語言英式英語
關鍵詞absolute worst-case ratio; bin packing; linear time algorithm
Web of Science 學科類別Operations Research & Management Science; OPERATIONS RESEARCH & MANAGEMENT SCIENCE

上次更新時間 2021-21-02 於 01:26