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: Csirik, Frenk, Lebbe and Zhang[2]: 16–19 present the following simple algorithm for 2/3 approximation.
Suppose the bin size is 1 and there are n items.
the number of bins in the optimal solution, and by
the number of full bins in the bidirectional filling algorithm.
is at least 1, but if the final item is removed from it, then the remaining sum is smaller than 1.
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.
BDF initializes the first bin with the largest item and fills it with the
items can cover bins only in triplets, so all in all
Csirik, Frenk, Lebbe and Zhang[2]: 19–24 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.
TCF attains the optimal outcome, since it initializes all
the number of bins in the optimal solution, and by
the number of full bins in the three-classes filling algorithm.
TCF initializes the first bin with the largest two items, and fills it with the
items can cover bins only in groups of four, so all in all
Csirik, Johnson and Kenyon[3] present an asymptotic PTAS.
The algorithm solves a variant of the configuration linear program, with
This algorithm is only theoretically interesting, since in order to get better than 3/4 approximation, we must take
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[4] present an asymptotic FPTAS.
is the runtime complexity of the best available algorithm for matrix inversion (currently, around
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.
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.