Lower bounds and algorithms for the minimum cardinality bin covering problem

DOI10.1016/J.EJOR.2016.06.068MaRDI QIDQ1752204zbMATH OpenOpenAlexFDO

Authors Rico Walter, Alexander Lawrinenko

Publication date 24 May 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2016.06.068

zbMATH Keywords

bin coveringbranch-and-boundheuristicslower boundsminimum cardinality

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Upper bounds and algorithms for the maximum cardinality bin packing problem.
• Bin covering with cardinality constraints
• A min-cost bin covering problem and its algorithm
• An asymptotically exact algorithm for the high-multiplicity bin packing problem
• Cardinality constrained bin-packing problems

Cites work

• A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital
• An exact algorithm for the dual bin packing problem
• Approximating covering integer programs with multiplicity constraints
• Approximation algorithms for covering/packing integer programs
• Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem
• Bin completion algorithms for multicontainer packing, Knapsack, and covering problems
• Bin covering with cardinality constraints
• Bin packing: Maximizing the number of pieces packed
• Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem
• Class constrained bin covering
• Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation
• Dual bin packing with items of random sizes
• scientific article; zbMATH DE number 3643036 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Integer Rounding for Polymatroid and Branching Optimization Problems
• Maximizing the minimum completion time on parallel machines
• On a dual version of the one-dimensional bin packing problem
• On the sum minimization version of the online bin covering problem
• Performance of Heuristics for a Computer Resource Allocation Problem
• Probabilistic analysis of a heuristic for the dual bin packing problem
• Probabilistic bounds for dual bin-packing
• Selected Topics in Column Generation
• The modified integer round-up property of the one-dimensional cutting stock problem
• Two simple algorithms for bin covering
• Upper bounds and algorithms for the maximum cardinality bin packing problem.
• Using extra dual cuts to accelerate column generation
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

Cited in

(7)

• Bin covering with cardinality constraints
• A lower bound for the coverability problem in acyclic pushdown VAS
• Two simple algorithms for bin covering
• scientific article; zbMATH DE number 5936584 (Why is no real title available?)
• scientific article; zbMATH DE number 1855660 (Why is no real title available?)
• A solution construction method for solving a specified covering problem
• Exact combinatorial algorithms for solving the bin covering problems with strong divisibility and rejection profit

This page was built for publication: Lower bounds and algorithms for the minimum cardinality bin covering problem

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