Computing the asymptotic worst-case of bin packing lower bounds
作者： Teodor Gabriel Crainic , Guido Perboli , Miriam Pezzuto , Roberto Tadei
DOI: 10.1016/J.EJOR.2005.07.032
关键词:
摘要: Abstract This paper addresses the issue of computing asymptotic worst-case lower bounds for Bin Packing Problem. We introduce a general result that allows to bound performance any problem and derive first time well-known L 3 by Martello Toth. also show easily several proposed in literature.
core.ac.uk
elsevier.com
sci-hub.se 参考文章(11)
David S. Johnson, Near-optimal bin packing algorithms Massachusetts Institute of Technology. ,(1973)
Dorit S. Hochba, Approximation Algorithms for NP-Hard Problems ,(1996)
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations ,(1990)
Jean-Marie Bourjolly, Vianney Rebetez, An analysis of lower bound procedures for the bin packing problem Computers & Operations Research. ,vol. 32, pp. 395- 405 ,(2005) , 10.1016/S0305-0548(03)00244-2
Joseph Y.-T. Leung, Chung-Lun Li, An asymptotic approximation scheme for the concave cost bin packing problem European Journal of Operational Research. ,vol. 191, pp. 582- 586 ,(2008) , 10.1016/J.EJOR.2007.08.031
Teodor Gabriel Crainic, Guido Perboli, Miriam Pezzuto, Roberto Tadei, New bin packing fast lower bounds Computers & Operations Research. ,vol. 34, pp. 3439- 3457 ,(2007) , 10.1016/J.COR.2006.02.007
Silvano Martello, Paolo Toth, Lower bounds and reduction procedures for the bin packing problem Discrete Applied Mathematics. ,vol. 28, pp. 59- 70 ,(1990) , 10.1016/0166-218X(90)90094-S
Martine Labbé, Gilbert Laporte, Hélène Mercure, Capacitated Vehicle Routing on Trees Operations Research. ,vol. 39, pp. 616- 622 ,(1991) , 10.1287/OPRE.39.4.616
Gerhard Wäscher, Heike Haußner, Holger Schumann, An improved typology of cutting and packing problems European Journal of Operational Research. ,vol. 183, pp. 1109- 1130 ,(2007) , 10.1016/J.EJOR.2005.12.047
Sándor P. Fekete, Jörg Schepers, New Classes of Lower Bounds for Bin Packing Problems integer programming and combinatorial optimization. pp. 257- 270 ,(1998) , 10.1007/3-540-69346-7_20