On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis

DOI10.1007/11809678_33MaRDI QIDQ3591341zbMATH OpenOpenAlexFDO

Authors Wun-Tat Chan, Prudence W. H. Wong, Fencol C. C. Yung

Publication date 10 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11809678_33

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On dynamic bin packing: An improved lower bound and resource augmentation analysis
• scientific article; zbMATH DE number 2086631
• scientific article; zbMATH DE number 1670832
• scientific article; zbMATH DE number 6767525
• Fully dynamic bin packing revisited
• Resource augmentation for online bounded space bin packing
• An improved lower bound for the bin packing problem
• Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems
• Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems
• An \(\frac{8}{3}\) lower bound for online dynamic bin packing

Cited in

(9)

• A fundamental restriction on fully dynamic maintenance of bin packing
• Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time
• scientific article; zbMATH DE number 6767525 (Why is no real title available?)
• On dynamic bin packing: An improved lower bound and resource augmentation analysis
• Tight results for next fit and worst fit with resource augmentation
• An \(\frac{8}{3}\) lower bound for online dynamic bin packing
• Dynamic bin packing of unit fractions items
• Automata, Languages and Programming
• Resource augmentation for online bounded space bin packing

This page was built for publication: On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis

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