Operations research problem of packing items into the largest number of bins
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.
The problem is NP-hard, but there are various efficient approximation algorithms:
The bidirectional bin-filling algorithm.
Csirik, Frenk, Lebbe and Zhang present the following simple algorithm for 2/3 approximation. Suppose the bin size is 1 and there are "n" items.
For any instance "I", denote by formula_2 the number of bins in the optimal solution, and by formula_3 the number of full bins in the bidirectional filling algorithm. Then formula_4, or equivalently, formula_5. 
Proof.
For the proof, the following terminology is used.
The sum of each bin formula_10 is at least 1, but if the final item is removed from it, then the remaining sum is smaller than 1. Each of the first "formula_11" bins formula_12 contains an initial item, possibly some middle items, and a final item. Each of the last formula_9 bins formula_14 contains only an initial item and a final item, since both of them are larger than 1/2 and their sum is already larger than 1.
The proof considers two cases.
The easy case is formula_15, that is, all final items are smaller than 1/2. Then, the sum of every filled formula_16 is at most 3/2, and the sum of remaining items is at most 1, so the sum of all items is at most formula_17. On the other hand, in the optimal solution the sum of every bin is at least 1, so the sum of all items is at least formula_2. Therefore, formula_19 as required.
The hard case is formula_20, that is, some final items are larger than 1/2. We now prove an upper bound on formula_2 by presenting it as a sum formula_22 where:
We focus first on the optimal bins in formula_26 and formula_27. We present a bijection between the items in each such bin to some items in formula_10 which are at least as valuable.
We now focus on the optimal bins in formula_27 and formula_36. 
Tightness.
The 2/3 factor is tight for BDF. Consider the following instance (where formula_44 is sufficiently small):formula_45BDF initializes the first bin with the largest item and fills it with the formula_46 smallest items. Then, the remaining formula_46 items can cover bins only in triplets, so all in all formula_48 bins are filled. But in OPT one can fill formula_49 bins, each of which contains two of the middle-sized items and two small items.
Three-classes bin-filling algorithm.
Csirik, Frenk, Lebbe and Zhang present another algorithm that attains a 3/4 approximation. The algorithm orders the items from large to small, and partitions them into three classes:
The algorithm works in two phases. Phase 1:
Phase 2:
In the above example, showing the tightness of BDF, the sets are:formula_50TCF attains the optimal outcome, since it initializes all formula_49 bins with pairs of items from Y, and fills them with pairs of items from Z.
For any instance "I", denote by formula_2 the number of bins in the optimal solution, and by formula_53 the number of full bins in the three-classes filling algorithm. Then formula_54.
The 3/4 factor is tight for TCF. Consider the following instance (where formula_44 is sufficiently small):
formula_56
TCF initializes the first bin with the largest two items, and fills it with the formula_57 smallest items. Then, the remaining formula_57 items can cover bins only in groups of four, so all in all formula_59 bins are filled. But in OPT one can fill formula_60 bins, each of which contains 3 middle-sized items and 3 small items.
Polynomial-time approximation schemes.
Csirik, Johnson and Kenyon present an asymptotic PTAS. It is an algorithm that, for every "ε" ;0, fills at least formula_61 bins if the sum of all items is more than formula_62, and at least formula_63 otherwise. It runs in time formula_64. The algorithm solves a variant of the configuration linear program, with formula_65variables and formula_66 constraints. This algorithm is only theoretically interesting, since in order to get better than 3/4 approximation, we must take formula_67, and then the number of variables is more than formula_68.
They also present algorithms for the "online" version of the problem. In the online setting, it is not possible to get an asymptotic worst-case approximation factor better than 1/2. However, there are algorithms that perform well in the average case.
Jansen and Solis-Oba present an asymptotic FPTAS. It is an algorithm that, for every "ε" ;0, fills at least formula_69 bins if the sum of all items is more than formula_70 (if the sum of items is less than that, then the optimum is at most formula_71 anyway). It runs in time formula_72, where formula_73 is the runtime complexity of the best available algorithm for matrix inversion (currently, around formula_74). This algorithm becomes better than the 3/4 approximation already when formula_75, and in this case the constants are reasonable - about formula_76. 
Performance with divisible item sizes.
An important special case of bin covering is that the item sizes form a "divisible sequence" (also called "factored"). A special case of divisible item sizes occurs in memory allocation in computer systems, where the item sizes are all powers of 2. If the item sizes are divisible, then some of the heuristic algorithms for bin covering find an optimal solution.Sec.5
Related problems.
In the fair item allocation problem, there are different people each of whom attributes a different value to each item. The goal is to allocate to each person a "bin" full of items, such that the value of each bin is at least a certain constant, and as many people as possible receive a bin. Many techniques from bin covering are used in this problem too.
References.
 ;templatestyles src="Reflist/styles.css" / ;