A 5/4 Linear Time Bin Packing Algorithm

✍ Scribed by József Békési; Gábor Galambos; Hans Kellerer

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 195 KB
• Volume: 60
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1667

✦ Synopsis

In 1985, Martel published a linear time algorithm with a 4 3 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 5 4 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 5 4 asymptotic worst-case ratio.