In the bin covering problem, given a list L = (α_1, …, α_n) of items with sizes s_L(α_i) ∈ (0,1), the goal is to find a packing of the items into bins such that the number of bins that receive items of total size at least 1 is maximized. This is a dual problem to the classical bin packing problem. In this paper we present the first asymptotic fully polynomial-time approximation scheme (AFPTAS) for the bin covering problem.
展开▼
