Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms
作者： G. Galambos , A. van Vliet
DOI: 10.1007/BF02246509
关键词: Line (geometry) 、 Simple (abstract algebra) 、 Upper and lower bounds 、 Worst case ratio 、 Mathematics 、 Computer communication networks 、 Combinatorics 、 Bin packing problem 、 Algorithm 、 Theoretical computer science 、 Computational Theory and Mathematics 、 Software 、 Numerical analysis 、 Computational mathematics 、 Computer Science Applications
摘要: In this paper we discuss lower bounds for the asymptotic worst case ratio of on-line algorithms different kind bin packing problems. Recently, Galambos and Frenk gave a simple proof 1.536 ... bound 1-dimensional problem. Following their ideas, present general technique that can be used to derive other problems as well. We apply prove new 2-dimensional (1.802...) 3-dimensional (1.974...)
springer.com
sci-hub.se 参考文章(9)
Hans Kellerer, Gerhard J. Woeginger, Gábor Galambos, A Lower Bound for On-Line Vector-Packing Algorithms. Acta Cybernetica. ,vol. 11, pp. 23- 34 ,(1993)
G. Galambos, A 1.6 lower-bound for the two-dimensional on-line rectangle bin-packing Acta Cybernetica. ,vol. 10, pp. 21- 24 ,(1991)
André van Vliet, An improved lower bound for on-line bin packing algorithms Information Processing Letters. ,vol. 43, pp. 277- 284 ,(1992) , 10.1016/0020-0190(92)90223-I
Michael Randolph Garey, Johnson: computers and intractability: a guide to the theory of np- completeness (freeman ,(1979)
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Michael B. Richey, Improved bounds for harmonic-based bin packing algorithms Discrete Applied Mathematics. ,vol. 34, pp. 203- 227 ,(1991) , 10.1016/0166-218X(91)90087-D
G. Galambos, J.B.G. Frenk, A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case Discrete Applied Mathematics. ,vol. 41, pp. 173- 178 ,(1993) , 10.1016/0166-218X(93)90037-O
János Csirik, André van Vliet, An on-line algorithm for multidimensional bin packing Operations Research Letters. ,vol. 13, pp. 149- 158 ,(1993) , 10.1016/0167-6377(93)90004-Z
Frank M. Liang, A lower bound for on-line bin packing Information Processing Letters. ,vol. 10, pp. 76- 79 ,(1980) , 10.1016/S0020-0190(80)90077-0