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

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, Batched bin packing, 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