Approximation algorithms for generalized and variable-sized bin covering

DOI10.1007/978-3-642-32512-0_17zbMATH Open1372.68299arXiv1109.3544OpenAlexW1930477728MaRDI QIDQ3167396FDOQ3167396

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)

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.

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

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

Mathematics Subject Classification ID

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

Cited In (8)

• Two simple algorithms for bin covering
• An asymptotic fully polynomial time approximation scheme for bin covering.
• Title not available (Why is that?)
• Bin covering with a general profit function: approximability results
• Bin covering with cardinality constraints
• Better approximation algorithms for bin covering
• Title not available (Why is that?)
• 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)