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 <a href="/facts/Bin_packing_problem/T67Qe934">bin packing problem</a>: 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.
The problem is <a href="/facts/NP-hardness/mQeNPv4R">NP-hard</a>, but there are various efficient <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithms</a>:

<ul><li>Algorithms covering at least 1/2, 2/3 or 3/4 of the optimum bin count asymptotically, running in time 
 
 
 
 O
 (
 n
 )
 ,
 O
 (
 n
 log
 ⁡
 n
 )
 ,
 O
 (
 n
 
 
 log
 
 
 2
 
 
 n
 )
 
 
 {\displaystyle O(n),O(n\log n),O(n{\log }^{2}n)}
 
 respectively.</li>
<li>An asymptotic <a href="/facts/Polynomial-time_approximation_scheme/52Chjx9y">PTAS</a>, 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.</li>
<li>An asymptotic <a href="/facts/Fully_polynomial-time_approximation_scheme/52Chjx9y">FPTAS</a>.</li></ul>

Bin covering problem open-in-new

Bin covering problem