Bin covering problem: Difference between revisions

Content deleted Content added

Inline

Revision as of 03:06, 20 November 2020

In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used. ^[1]^[2]^[3]^[4]

This problem is a dual of the bin packing problem: in bin covering, the bin sizes are bounded from below and the goal is to maximize their number; in bin packing, the bin sizes are bounded from above and the goal is to minimize their number.

This computer science article is a stub. You can help Wikipedia by expanding it.

References

^ Assmann, S. F; Johnson, D. S; Kleitman, D. J; Leung, J. Y. -T (1984-12-01). "On a dual version of the one-dimensional bin packing problem". Journal of Algorithms. 5 (4): 502–525. doi:10.1016/0196-6774(84)90004-X. ISSN 0196-6774.
^ Csirik, János (1999-01-01). "Two simple algorithms for bin covering". Acta Cybernetica. 14 (1): 13–25. ISSN 2676-993X.
^ Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). "Better approximation algorithms for bin covering". Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. SODA '01. Washington, D.C., USA: Society for Industrial and Applied Mathematics: 557–566. ISBN 978-0-89871-490-6.
^ Jansen, Klaus; Solis-Oba, Roberto (2002-11-21). "An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering". Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC '02. Berlin, Heidelberg: Springer-Verlag: 175–186. ISBN 978-3-540-00142-3.

[1] Assmann, S. F; Johnson, D. S; Kleitman, D. J; Leung, J. Y. -T (1984-12-01). "On a dual version of the one-dimensional bin packing problem". Journal of Algorithms. 5 (4): 502–525. doi:10.1016/0196-6774(84)90004-X. ISSN 0196-6774.

[2] Csirik, János (1999-01-01). "Two simple algorithms for bin covering". Acta Cybernetica. 14 (1): 13–25. ISSN 2676-993X.

[3] Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). "Better approximation algorithms for bin covering". Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. SODA '01. Washington, D.C., USA: Society for Industrial and Applied Mathematics: 557–566. ISBN 978-0-89871-490-6.

[4] Jansen, Klaus; Solis-Oba, Roberto (2002-11-21). "An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering". Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC '02. Berlin, Heidelberg: Springer-Verlag: 175–186. ISBN 978-3-540-00142-3.

[1]

[2]

[3]

[4]