On dynamic bin packing: An improved lower bound and resource augmentation analysis

DOI10.1007/S00453-008-9185-ZzbMath1172.68066OpenAlexW1999039393MaRDI QIDQ1014797

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

Publication date: 29 April 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9185-z

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Dynamic bin packing with unit fraction items revisited ⋮ Dynamic multi-dimensional bin packing ⋮ Fully dynamic bin packing revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bin packing with divisible item sizes
• An improved lower bound for on-line bin packing algorithms
• Bin packing with discrete item sizes, part II: Tight bounds on First Fit
• On the online bin packing problem
• Windows scheduling as a restricted version of bin packing
• Dynamic Bin Packing
• Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
• Speed is as powerful as clairvoyance
• Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings
• Resource augmentation for online bounded space bin packing
• Approximation and Online Algorithms
• Automata, Languages and Programming

This page was built for publication: On dynamic bin packing: An improved lower bound and resource augmentation analysis