A 5/4 Linear Time Bin Packing Algorithm

摘要

In 1985, Martel published a linear time algorithm with a 43 asymptotic worst-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 thereafter—according to the number of elements in certain subclasses—pairing the items in a clever way. In his paper Martel mentioned a natural generalization of this algorithm, that suggested a 54 algorithm. Although this seemed to be very simple, the improvement has not been realized until now. In this paper we present an algorithm which uses the ideas of Martel and has a 54 asymptotic worst-case ratio.