A 5/4 linear time bin packing algorithm

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.