On dynamic bin packing: An improved lower bound and resource augmentation analysis
DOI10.1007/S00453-008-9185-ZzbMATH Open1172.68066OpenAlexW1999039393MaRDI QIDQ1014797FDOQ1014797
Authors: Joseph Wun-Tat Chan, Prudence W. H. Wong, Fencol C. C. Yung 
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
Recommendations
Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Speed is as powerful as clairvoyance
- On the online bin packing problem
- An improved lower bound for on-line bin packing algorithms
- Dynamic Bin Packing
- Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
- Title not available (Why is that?)
- Windows scheduling as a restricted version of bin packing
- Bin packing with divisible item sizes
- Bin packing with discrete item sizes, part II: Tight bounds on First Fit
- Resource augmentation for online bounded space bin packing
- Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings
- Approximation and Online Algorithms
- Automata, Languages and Programming
Cited In (11)
- A fundamental restriction on fully dynamic maintenance of bin packing
- Title not available (Why is that?)
- Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time
- Competitive multi-dimensional dynamic bin packing via L-shape bin packing
- Dynamic multi-dimensional bin packing
- An \(\frac{8}{3}\) lower bound for online dynamic bin packing
- Dynamic bin packing with unit fraction items revisited
- Worst-case analysis of heuristic approaches for the temporal bin packing problem with fire-ups
- Fully dynamic bin packing revisited
- Automata, Languages and Programming
- On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis
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 Q1014797)
