Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps

DOI10.1137/S0097539794276749zbMath0915.68078MaRDI QIDQ4210166

Zoran Ivković, Errol L. Lloyd

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

bin packing; fully dynamic algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

68W10: Parallel algorithms in computer science

68P05: Data structures

Related Items

Unnamed Item, A Robust AFPTAS for Online Bin Packing with Polynomial Migration, Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time, Semi-on-line bin packing: a short overview and a new lower bound, A fundamental restriction on fully dynamic maintenance of bin packing, Resource augmented semi-online bounded space bin packing, A robust APTAS for the classical bin packing problem, Improved lower bounds for semi-online bin packing problems, On dynamic bin packing: An improved lower bound and resource augmentation analysis, Dynamic bin packing with unit fraction items revisited, Batched bin packing, Fully dynamic bin packing revisited, Dynamic bin packing of unit fractions items, On-line bin packing with restricted repacking, A survey on combinatorial optimization in dynamic environments

Cites Work

• A 71/60 theorem for bin packing
• Parallel approximation algorithms for bin packing
• Bin packing can be solved within 1+epsilon in linear time
• Analysis of a Compound Bin Packing Algorithm
• Dynamic Bin Packing
• A simple on-line bin-packing algorithm
• New Algorithms for Bin Packing
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• On-line bin packing in linear time
• Reducibility among Combinatorial Problems
• A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs