New lower bounds for certain classes of bin packing algorithms

详细信息    查看全文

• 作者：Já ; nos Balogh ^{balogh@jgypk.u-szeged.hu} ; Jó ; zsef Bé ; ké ; si ; ^{bekesi@jgypk.u-szeged.hu} ; Gá ; bor Galambos ^{galambos@jgypk.u-szeged.hu}
• 关键词：Bin packing ; On-line algorithm ; Worst-case behavior ; Lower bound
• 刊名：Theoretical Computer Science
• 出版年：2012
• 出版时间：6 July, 2012
• 年：2012
• 卷：440-441
• 期：Complete
• 页码：1-13
• 全文大小：238 K

文摘

On-line algorithms have been extensively studied for the one-dimensional bin packing problem. In this paper, we investigate two classes of one-dimensional bin packing algorithms, and we give better lower bounds for their asymptotic worst-case behavior. For on-line algorithms so far the best lower bound was given by van Vliet in (1992) . He proved that there is no on-line bin packing algorithm with better asymptotic performance ratio than 1.54014? In this paper, we give an improvement on this bound?to and we investigate the parametric case as well. For those lists where the elements are preprocessed according to their sizes in non-increasing order, Csirik et?al. (1983)? proved that no on-line algorithm can have an asymptotic performance ratio smaller than . We improve this result to .