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 asymptotically, running in time respectively.[1][2]
- An asymptotic PTAS, 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 FPTAS.[4]
- ^ a b 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; 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.
- ^ 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. 2518. Berlin, Heidelberg: Springer-Verlag: 175–186. doi:10.1007/3-540-36136-7_16. ISBN 978-3-540-00142-3.