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 programming; Asymptotic approximation scheme; Bin covering

Mathematics Subject Classification ID

90C05: Linear programming

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Ordinal Maximin Share Approximation for Goods, Online Bin Covering with Limited Migration, Online bin covering with advice, The generalized assignment problem with minimum quantities, An improved approximation scheme for variable-sized bin packing, Selfish bin covering, Packing resizable items with application to video delivery over wireless networks, Approximation algorithms for general packing problems and their application to the multicast congestion problem, 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, Hardness of approximation for orthogonal rectangle packing and covering problems, Irreducible bin packing and normality in routing open shop, 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, Online bin covering with limited migration, An Incentive Mechanism for Selfish Bin Covering

Cites Work

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