Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems

DOI10.1007/S00453-008-9202-2MaRDI QIDQ2379919zbMATH OpenOpenAlexFDO

Authors Mingen Lin, Yang Yang, Jinhui Xu

Publication date 23 March 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-008-9202-2

zbMATH Keywords

approximation algorithmspatternlazy bin coveringmaximum resource bin packing

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems
• On lazy bin covering and packing problems
• On Lazy Bin Covering and Packing Problems
• Fundamentals of Computation Theory
• The maximum resource bin packing problem

Cites work

• A 71/60 theorem for bin packing
• Analysis of a Compound Bin Packing Algorithm
• Approximation schemes for packing with item fragmentation
• Better approximation algorithms for bin covering
• Bounded space on-line bin packing: Best is better than first
• Improved Space for Bounded-Space, On-Line Bin-Packing
• On Lazy Bin Covering and Packing Problems
• On a dual version of the one-dimensional bin packing problem
• On two class-constrained versions of the multiple knapsack problem
• Repacking helps in bounded space on-line bin-packing
• Resource constrained scheduling as generalized bin packing
• The Parametric Behavior of the First-Fit Decreasing Bin Packing Algorithm
• The maximum resource bin packing problem
• Windows scheduling as a restricted version of bin packing

Cited in

(10)

• Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems
• Tight approximations for resource constrained scheduling and bin packing
• Hardness of lazy packing and covering
• More on ordered open end bin packing
• Open-end bin packing: new and old analysis approaches
• On lazy bin covering and packing problems
• On Lazy Bin Covering and Packing Problems
• Online lazy bureaucrat scheduling with a machine deadline
• A note on a variant of the online open end bin packing problem
• On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis

This page was built for publication: Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems

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