Approximation Algorithms for Variable-Sized and Generalized Bin Covering

Details Approximation Algorithms for Variable-Sized and Generalized Bin Covering Approximation Algorithms for Variable-Sized and Generalized Bin Covering

2011-09-16

arxiv.org/abs/1109.3544v2

Computer Science

Data Structures and Algorithms

Improved Approximation Guarantee for Generalized Bin Covering and added AFPTAS

Scientific paper

We consider the Generalized Bin Covering (GBC) 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 covered if the set of items assigned to it has total size at least the demand $d_i$. In that case, the profit of $p_i$ is earned and the objective is to maximize the total profit. To the best of our knowledge, only the cases $p_i = d_i = 1$ (Bin Covering) and $p_i = d_i$ (Variable-Sized Bin Covering (VSBC)) 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. Clearly, the unit supply model is a generalization of the infinite supply model. To the best of our knowledge the unit supply model has not been studied yet. Our results for the unit supply model hold not only asymptotically, but for all instances. This contrasts most of the previous work on \prob{Bin Covering}. We prove that there is a combinatorial 5-approximation algorithm for GBC with unit supply, which has running time $\bigO{nm\sqrt{m+n}}$. Furthermore, for VSBC we show that the natural and fast Next Fit Decreasing ($\NFD$) algorithm is a 9/4-approximation in the unit supply model. The bound is tight for the algorithm and close to being best-possible. We show that there is an AFPTAS for VSBC in the \emph{infinite} supply model.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithms for Variable-Sized and Generalized Bin Covering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Algorithms for Variable-Sized and Generalized Bin Covering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for Variable-Sized and Generalized Bin Covering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-534508