Approximation Algorithms for Generalized and Variable-Sized Bin Covering

We consider the Generalized Bin Covering problem: We are given m bin types, where each bin of type i has profit p i and demand d i . Furthermore, there are n items, where item j has size s j . A bin of type i is said to be covered if the set of items assigned to it has total size of at least d i . For earning profit p i a bin of type i has to be covered. The objective is to maximize the total profit. Only the cases p i = d i = 1 (Bin Covering) and p i = d i (Variable-Sized Bin Covering) have been treated before. We study two models of bin supply: In the unit supply model, we have exactly one bin of each type, i. e., we have individual bins. By contrast, in the infinite supply model, we have arbitrarily many bins of each type. Both versions of the problem are NP-hard and can not be approximated better than 2 in polynomial time, unless P = NP.