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

DOI10.1007/S00453-008-9202-2zbMATH Open1191.68870OpenAlexW1965153006MaRDI QIDQ2379919FDOQ2379919

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

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

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)

Cites Work

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