Better approximation algorithms for bin covering
Bin covering takes as input a list of items with sizes in \((0,1) \) and places them into bins of unit demand so as to maximize the number of bins whose demand is satisfied. This is in a sense a dual problem to the classical one-dimensional bin packing problem, but has for many years lagged behind the latter in terms of the quality of the best approximation algorithms. We design algorithms for this problem that close the gap, both in terms of worst- and average-case results. We present (1) the first asymptotic approximation scheme for the offline version, (2) algorithms that have bounded worst-case behavior for instances with discrete item sizes and expected behavior that is asymptotically optimal for all discrete ``perfect-packing distributions (ones for which optimal packings have sublinear expected waste), and (3) a learning algorithm that has asymptotically optimal expected behavior for all discrete distributions. The algorithms of (2) and (3) are based on the recently-developed online Sum-of-Squares algorithm for bin packing. We also present experimental analysis comparing the algorithms of (2) and suggsting that one of them, the Sum-of-Squares-with-Threshold algorithm, performs quite well even for discrete distributions that do not have the perfect-packing property.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].
- Online bin covering: expectations vs. guarantees
- Online Bin Covering: Expectations vs. Guarantees
- Approximation algorithms for generalized and variable-sized bin covering
- Probabilistic analysis of the dual next-fit algorithm for bin covering
- Optimal on-line algorithms for variable-sized bin covering
- Hardness of lazy packing and covering
- Hardness of approximation for orthogonal rectangle packing and covering problems
- Bounded-space online bin cover
- An asymptotic fully polynomial time approximation scheme for bin covering.
- Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems
- Approximation and online algorithms for multidimensional bin packing: a survey
- Bin covering with cardinality constraints
- Bin packing problems with rejection penalties and their dual problems
- The maximum resource bin packing problem
- The generalized assignment problem with minimum quantities
- Online bin covering with limited migration
- Two simple algorithms for bin covering
- Probabilistic analysis of the dual next-fit algorithm for bin covering
- Better bin packing approximations via discrepancy theory
- Bin covering with delivery and solving it with evolution of algorithms
- An incentive mechanism for selfish bin covering
- Bin covering with a general profit function: approximability results
- Approximation algorithms for generalized and variable-sized bin covering
- scientific article; zbMATH DE number 1979497 (Why is no real title available?)
- Online Bin Covering with Limited Migration
- Ordinal Maximin Share Approximation for Goods
- Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing
- The bin covering with delivery problem, extended investigations for the online case
- Selfish bin covering
- Online bin covering with frequency predictions
- Exact combinatorial algorithms for solving the bin covering problems with strong divisibility and rejection profit
- Packing resizable items with application to video delivery over wireless networks
- Class constrained bin covering
- Asymptotic fully polynomial approximation schemes for variants of open-end bin packing
- On the sum minimization version of the online bin covering problem
This page was built for publication: Better approximation algorithms for bin covering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2768348)
