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

DOI10.1007/S00453-008-9185-ZMaRDI QIDQ1014797zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis
• An \(\frac{8}{3}\) lower bound for online dynamic bin packing
• Automata, Languages and Programming
• Online bin packing with resource augmentation
• Dynamic bin packing of unit fractions items

Cites work

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

Cited in

(11)

• 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?)
• 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)