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


Times Cited
Web of Science9WOS source URL (as at 18/01/2021) Click here for the latest count
Altmetrics Information
.

Other information
AbstractSimchi-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.
All Author(s) ListZhang GC, Cai XQ, Wong CK
Journal nameOperations Research Letters
Year2000
Month6
Day1
Volume Number26
Issue Number5
PublisherELSEVIER SCIENCE BV
Pages217 - 222
ISSN0167-6377
eISSN1872-7468
LanguagesEnglish-United Kingdom
Keywordsabsolute worst-case ratio; bin packing; linear time algorithm
Web of Science Subject CategoriesOperations Research & Management Science; OPERATIONS RESEARCH & MANAGEMENT SCIENCE

Last updated on 2021-19-01 at 01:45