An asymptotic approximation scheme for the concave cost bin packing problem
作者： Joseph Y.-T. Leung , Chung-Lun Li
DOI: 10.1016/J.EJOR.2007.08.031
关键词:
摘要: Abstract We consider a generalized one-dimensional bin packing model in which the cost of is nondecreasing concave function utilization bin. show that for any given positive constant ϵ , there exists polynomial-time approximation algorithm with an asymptotic worst-case performance ratio no more than 1 + .
core.ac.uk
elsevier.com
sci-hub.se 参考文章(10)
Dorit S. Hochbaum, Various notions of approximations: good, better, best, and more Approximation algorithms for NP-hard problems. pp. 346- 446 ,(1996)
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)
Dorit S. Hochba, Approximation Algorithms for NP-Hard Problems ,(1996)
Jangha Kang, Sungsoo Park, Algorithms for the variable sized bin packing problem European Journal of Operational Research. ,vol. 147, pp. 365- 372 ,(2003) , 10.1016/S0377-2217(02)00247-3
Cláudio Alves, J.M. Valério de Carvalho, Accelerating column generation for variable sized bin-packing problems European Journal of Operational Research. ,vol. 183, pp. 1333- 1352 ,(2007) , 10.1016/J.EJOR.2005.07.033
Chung-Lun Li, Zhi-Long Chen, Bin‐packing problem with concave costs of bin utilization Naval Research Logistics. ,vol. 53, pp. 298- 308 ,(2006) , 10.1002/NAV.20142
Teodor Gabriel Crainic, Guido Perboli, Miriam Pezzuto, Roberto Tadei, Computing the asymptotic worst-case of bin packing lower bounds European Journal of Operational Research. ,vol. 183, pp. 1295- 1303 ,(2007) , 10.1016/J.EJOR.2005.07.032
Jian Yang, Joseph Y.-T. Leung, The Ordered Open-End Bin-Packing Problem Operations Research. ,vol. 51, pp. 759- 770 ,(2003) , 10.1287/OPRE.51.5.759.16753
Narendra Karmarkar, Richard M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). pp. 312- 320 ,(1982) , 10.1109/SFCS.1982.61
W. Fernandez de la Vega, G. S. Lueker, Bin packing can be solved within 1 + ε in linear time Combinatorica. ,vol. 1, pp. 349- 355 ,(1981) , 10.1007/BF02579456