Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms

被引：0

作者：

Galambos, G. ^{[1
]}

van Vliet, A. ^{[1
]}

机构：

[1] IGYTF, Szeged, Hungary

来源：

Computing (Vienna/New York) | 1994年 / 52卷 / 03期

关键词：

Combinatorial mathematics - Online systems - Three dimensional;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

In this paper we discuss lower bounds for the asymptotic worst case ratio of on-line algorithms for different kind of bin packing problems. Recently, Galambos and Frenk gave a simple proof of the 1.536 ... lower bound for the 1-dimensional bin packing problem. Following their ideas, we present a general technique that can be used to derive lower bounds for other bin packing problems as well. We apply this technique to prove new lower bounds for the 2-dimensional (1.802...) and 3-dimensional (1.974...) bin packing problem.

引用

页码：281 / 297