An exact algorithm for the dual bin packing problem
作者： Martine Labbé , Gilbert Laporte , Silvano Martello
DOI: 10.1016/0167-6377(94)00060-J
关键词:
摘要: In the Dual Bin Packing Problem (DBP), there is an unlimited number of bins identical capacity, and unsplittable items given weights. The aim to pack in as many possible so that total weight each bin at least equal its capacity. This article proposes reduction criteria, upper bounds, enumerative algorithm for DBP. Computational results are presented.
ulb.ac.be
elsevier.com
acm.org 
sci-hub.se 参考文章(11)
M Lucertini, G Ausiello, P Serafini, Algorithm Design for Computer System Design ,(1984)
E. G. Coffman, M. R. Garey, D. S. Johnson, Approximation Algorithms for Bin-Packing — An Updated Survey Algorithm Design for Computer System Design. pp. 49- 106 ,(1984) , 10.1007/978-3-7091-4338-4_3
Dean P. Foster, Rakesh V. Vohra, Probabilistic analysis of a heuristics for the dual bin packing problem Information Processing Letters. ,vol. 31, pp. 287- 290 ,(1989) , 10.1016/0020-0190(89)90088-4
J. Csirik, V. Totik, Online algorithms for a dual version of bin packing Discrete Applied Mathematics. ,vol. 21, pp. 163- 167 ,(1988) , 10.1016/0166-218X(88)90052-2
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
S.F Assmann, D.S Johnson, D.J Kleitman, J.Y.-T Leung, On a dual version of the one-dimensional bin packing problem Journal of Algorithms. ,vol. 5, pp. 502- 525 ,(1984) , 10.1016/0196-6774(84)90004-X
JohnL. Bruno, PeterJ. Downey, Probabilistic bounds for dual bin-packing Acta Informatica. ,vol. 22, pp. 333- 345 ,(1985) , 10.1007/BF00265685
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations ,(1990)
J Csirik, J.B.G Frenk, G Galambos, A.H.G Rinnooy Kan, Probabilistic analysis of algorithms for dual bin packing problems Journal of Algorithms. ,vol. 12, pp. 189- 203 ,(1991) , 10.1016/0196-6774(91)90001-F
János Csirik, Martine Labbé, Shuzhong Zhang, Johannes Bartholomeus Gerardus Frenk, Fast algorithms for dual bin packing Erasmus University of Rotterdam, Econometric Institute. ,(1990)