Bin covering problem

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.

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.[1]

The problem is NP-hard, but there are various efficient approximation algorithms:

  • Algorithms covering at least 1/2, 2/3 or 3/4 of the optimum bin count, running in time respectively.[1][2]
  • An asymptotic polynomial-time approximation scheme, algorithms with bounded worst-case behavior whose expected behavior is asymptotically-optimal for some discrete distributions, and a learning algorithm with asymptotically optimal expected behavior for all discrete distributions.[3]
  • An asymptotic fully polynomial-time approximation scheme.[4]

References
  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; J. B. G. Frenk and M. Labbé and S. Zhang (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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.