Approximation algorithms for generalized and variable-sized bin covering

DOI10.1007/978-3-642-32512-0_17MaRDI QIDQ3167396zbMATH OpenOpenAlexFDO

Authors Matthias Hellwig, Alexander Souza

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3544

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Abstract: 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 $$. 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.

Recommendations

• Optimal on-line algorithms for variable-sized bin covering
• Better approximation algorithms for bin covering
• scientific article; zbMATH DE number 1798171
• An improved approximation scheme for variable-sized bin packing
• Online variable sized covering

Cited in

(8)

• Bin covering with cardinality constraints
• Better approximation algorithms for bin covering
• scientific article; zbMATH DE number 1779967 (Why is no real title available?)
• Two simple algorithms for bin covering
• scientific article; zbMATH DE number 1979497 (Why is no real title available?)
• An asymptotic fully polynomial time approximation scheme for bin covering.
• Bin covering with a general profit function: approximability results
• A min-cost bin covering problem and its algorithm

This page was built for publication: Approximation algorithms for generalized and variable-sized bin covering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167396)