Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
From MaRDI portal
Publication:4210166
DOI10.1137/S0097539794276749zbMath0915.68078MaRDI QIDQ4210166
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Parallel algorithms in computer science (68W10) Data structures (68P05)
Related Items (17)
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 ⋮ Dynamic bin packing of unit fractions items ⋮ A survey on combinatorial optimization in dynamic environments ⋮ Dynamic bin packing with unit fraction items revisited ⋮ Dynamic Windows Scheduling with Reallocation ⋮ Fully dynamic maintenance of vertex cover ⋮ On-line bin packing with restricted repacking ⋮ Fully-Dynamic Bin Packing with Little Repacking ⋮ A fundamental restriction on fully dynamic maintenance of bin packing ⋮ Resource augmented semi-online bounded space bin packing ⋮ Batched bin packing ⋮ Fully dynamic bin packing revisited ⋮ 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 ⋮ A Robust AFPTAS for Online Bin Packing with Polynomial Migration
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
This page was built for publication: Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
