An asymptotic fully polynomial time approximation scheme for bin covering.

DOI10.1016/S0304-3975(03)00363-3zbMath1060.68111MaRDI QIDQ1426473

Roberto Solis-Oba, Klaus Jansen

Publication date: 14 March 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Linear programmingAsymptotic approximation schemeBin covering

Mathematics Subject Classification ID

Linear programming (90C05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (19)

Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Ordinal Maximin Share Approximation for Goods ⋮ An Incentive Mechanism for Selfish Bin Covering ⋮ Online bin covering with limited migration ⋮ Selfish bin covering ⋮ Bin covering with cardinality constraints ⋮ Approximation algorithms for general packing problems and their application to the multicast congestion problem ⋮ An improved approximation scheme for variable-sized bin packing ⋮ Irreducible bin packing and normality in routing open shop ⋮ Class constrained bin covering ⋮ Asymptotic fully polynomial approximation schemes for variants of open-end bin packing ⋮ Bin packing problems with rejection penalties and their dual problems ⋮ On the sum minimization version of the online bin covering problem ⋮ The maximum resource bin packing problem ⋮ Packing resizable items with application to video delivery over wireless networks ⋮ Online Bin Covering with Limited Migration ⋮ Online bin covering with advice ⋮ Hardness of approximation for orthogonal rectangle packing and covering problems ⋮ The generalized assignment problem with minimum quantities

Cites Work

• On a dual version of the one-dimensional bin packing problem
• Coordination Complexity of Parallel Price-Directive Decomposition
• Unnamed Item
• Unnamed Item

This page was built for publication: An asymptotic fully polynomial time approximation scheme for bin covering.