New lower bounds for the three-dimensional orthogonal bin packing problem
作者： Chung-Shou Liao , Chia-Hong Hsu
DOI: 10.1016/J.EJOR.2012.10.024
关键词: Square packing in a square 、 Bin packing problem 、 Point (geometry) 、 Generalization 、 Combinatorics 、 Combinatorial optimization 、 Discrete mathematics 、 Time complexity 、 Mathematics
摘要: Abstract In this paper, we consider the three-dimensional orthogonal bin packing problem, which is a generalization of well-known problem. We present new lower bounds for problem from combinatorial point view and demonstrate that they theoretically dominate all previous results literature. The comparison also done concerning asymptotic worst-case performance ratios. can be more efficiently computed in polynomial time. addition, study non-oriented model, allows items to rotated.
core.ac.uk
cccg.ca 
nsysu.edu.tw 参考文章(33)
Seiden, van Stee, New Bounds for Multidimensional Packing Algorithmica. ,vol. 36, pp. 261- 293 ,(2003) , 10.1007/S00453-003-1016-7
M. R. Garey, E. G. Coffman, D. S. Johnson, Approximation algorithms for bin packing: a survey Approximation algorithms for NP-hard problems. pp. 46- 93 ,(1996)
Jens Vygen, Bernhard Korte, Combinatorial Optimization: Theory and Algorithms ,(2012)
David S. Johnson, Near-optimal bin packing algorithms Massachusetts Institute of Technology. ,(1973)
S�ndor P. Fekete, J�rg Schepers, A General Framework for Bounds for Higher-Dimensional Orthogonal Packing Problems Mathematical Methods of Operations Research. ,vol. 60, pp. 311- 329 ,(2004) , 10.1007/S001860400376
Marco A. Boschetti, New lower bounds for the three-dimensional finite bin packing problem Discrete Applied Mathematics. ,vol. 140, pp. 241- 258 ,(2004) , 10.1016/J.DAM.2003.08.004
Mauro Dell'Amico, Silvano Martello, Daniele Vigo, A lower bound for the non-oriented two-dimensional bin packing problem Discrete Applied Mathematics. ,vol. 118, pp. 13- 24 ,(2002) , 10.1016/S0166-218X(01)00253-0
François Clautiaux, Cláudio Alves, José Valério de Carvalho, A survey of dual-feasible and superadditive functions Annals of Operations Research. ,vol. 179, pp. 317- 342 ,(2010) , 10.1007/S10479-008-0453-8
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
François Clautiaux, Antoine Jouglet, Joseph El Hayek, A new lower bound for the non-oriented two-dimensional bin-packing problem Operations Research Letters. ,vol. 35, pp. 365- 373 ,(2007) , 10.1016/J.ORL.2006.07.001