A 5/4 linear time bin packing algorithm

Citation
J. Bekesi et al., A 5/4 linear time bin packing algorithm, J COMPUT SY, 60(1), 2000, pp. 145-160
Citations number
6
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
ISSN journal
0022-0000 → ACNP
Volume
60
Issue
1
Year of publication
2000
Pages
145 - 160
Database
ISI
SICI code
0022-0000(200002)60:1<145:A5LTBP>2.0.ZU;2-F
Abstract
In 1985, Martel published a linear lime algorithm with a 4/3 asymptotic wor st-case ratio for the one-dimensional bin packing problem. The algorithm is based on a linear time classification of the sizes of the items, and there after-according to the number of elements in certain subclasses-pairing the items in a clever way. In his paper Martel mentioned a natural generalizat ion of this algorithm, that suggested a 5/4 algorithm. Although this seemed to be very simple, the improvement has not been realized until now. In thi s paper we present an algorithm which uses the ideas of Martel and has a 5/ 4 asymptotic worst-case ratio. (C) 2000 Academic Press.