×

zbMATH — the first resource for mathematics

Upper bounds and algorithms for the maximum cardinality bin packing problem. (English) Zbl 1033.90108
Summary: In the maximum cardinality bin packing problem, we are given \(m\) bins of capacity \(c\) and \(n\) items of weights \(w_i (i=1,\dots,n)\). The objective is to maximize the number of items packed into the \(m\) bins without exceeding bin capacities and without splitting items. Several upper bounds are derived. These are then embedded in an enumeration algorithm. Computational results indicate that the algorithm typically identifies an optimal solution within very low computing times.

MSC:
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bruno, J.L.; Downey, P.J., Probabilistic bounds for dual bin packing, Acta informatica, 22, 333-345, (1985) · Zbl 0569.68037
[2] Chekuri, C.; Khanna, S., A PTAS for the multiple knapsack problem, Proceedings of SODA’2000, 213-222, (2000) · Zbl 0952.90020
[3] Coffman, E.G.; Leung, J.Y.-T., Combinatorial analysis of an efficient algorithm for processor and storage allocation, SIAM journal on computing, 8, 202-217, (1979) · Zbl 0417.68022
[4] Coffman, E.G.; Leung, J.Y.-T.; Ting, D.W., Bin packing: maximizing the number of pieces packed, Acta informatica, 9, 263-271, (1978) · Zbl 0421.68065
[5] Ferreira, C.M.; Martin, A.; Weismantel, R., Solving multiple knapsack problems by cutting planes, SIAM journal on optimization, 6, 858-877, (1996) · Zbl 0856.90082
[6] Foster, D.P.; Vohra, R.V., Probabilistic analysis for heuristics for the dual bin packing problem, Information processing letters, 31, 287-290, (1989) · Zbl 0682.68045
[7] Kellerer, H., A polynomial time approximation scheme for the multiple knapsack problem, Random–approx’99, 51-62, (1999) · Zbl 0945.90050
[8] Labbé, M.; Laporte, G.; Martello, S., An exact algorithm for the dual bin packing problem, Operations research letters, 17, 9-18, (1995) · Zbl 0835.90077
[9] Martello, S.; Toth, P., Knapsack problems, (1990), Wiley Chichester · Zbl 0452.90047
[10] Martello, S.; Toth, P., Lower bounds and reduction procedures for the bin packing problem, Discrete applied mathematics, 28, 59-70, (1990) · Zbl 0704.90074
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.