Thursday, 14:15 - 14:40 h, Room: H 3010


Alexander Souza
Approximation algorithms for generalized and variable-sized bin covering

Coauthor: Matthias Hellwig


We consider the NP-hard Generalized Bin Covering problem: We are given m bin types, where each bin of type i has profit pi and demand di. There are n items, where item j has size sj. A bin of type i is covered if the set of items assigned to it has total size at least the demand di. Then the profit of pi is earned and the objective is to maximize the total profit. To the best of our knowledge, only the cases pi = di = 1 (Bin Covering) and pi = di (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 and in the infinite supply model, we have arbitrarily many bins of each type.
We prove that there is a combinatorial 5-approximation algorithm for Generalized Bin Covering with unit supply, which has running time O(nm√m+n). For Variable-Sized Bin Covering, we show that the Next Fit Decreasing (NFD) algorithm is a 9/4-approximation in the unit supply model. We also show that there is an AFPTAS for Variable-Sized Bin Covering in the infinite supply model.


Talk 3 of the invited session Thu.2.H 3010
"Scheduling, packing and covering" [...]
Cluster 1
"Approximation & online algorithms" [...]


  Online lending company provides a wide range of ways to get money by means of Tennessee Loans Online. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.