×

zbMATH — the first resource for mathematics

An exact algorithm for the dual bin packing problem. (English) Zbl 0835.90077
Summary: In the Dual Bin Packing Problem (DBP), there is an unlimited number of bins of identical capacity, and unsplittable items of given weights. The aim is to pack items in as many bins as possible so that the total weight of each bin is at least equal to its capacity. This article proposes reduction criteria, upper bounds, and an enumerative algorithm for the DBP. Computational results are presented.

MSC:
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Assmann, S.F., Problems in discrete applied mathematics, ()
[2] Assmann, S.F.; Johnson, D.S.; Kleitman, D.J.; Leung, J.Y.-T., On a dual version of the one-dimensional binpacking problem, J. algorithms, 5, 502-525, (1984) · Zbl 0556.68011
[3] Bruno, J.L.; Downey, P.J., Probabilistic bounds for dual bin packing, Acta inform., 22, 333-345, (1985) · Zbl 0569.68037
[4] Coffman, E.G.; Garey, M.R.; Johnson, D.S., Approximation algorithms for bin-packing-an updated survey, (), 49-106 · Zbl 0558.68062
[5] Csirik, J.; Frenk, J.B.G., A dual version of bin packing, Algorithms rev., 1, 87-95, (1990)
[6] Csirik, J.; Frenk, J.B.G.; Galambos, G.; Rinnooy Kan, A.H.G., Probabilistic analysis of algorithms for dual bin packing problems, J. algorithms, 12, 189-203, (1991) · Zbl 0734.68050
[7] Csirik, J.; Frenk, J.B.G.; Labbé, M.; Zhang, S., Fast algorithms for dual bin packing, () · Zbl 0724.68048
[8] Csirik, J.; Totik, V., Online algorithms for a dual version of bin packing, Discrete appl. math., 21, 163-167, (1988) · Zbl 0659.68069
[9] Foster, D.P.; Vohra, R.V., Probabilistic analysis of a heuristics for the dual bin packing problem, Inform. process. lett., 31, 287-290, (1989) · Zbl 0682.68045
[10] Garey, M.G.; Johnson, D.S., ()
[11] Martello, S.; Toth, P., Knapsack problems. algorithms and computer implementations, (1990), Wiley Chichester · Zbl 0708.68002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.