Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time
From MaRDI portal
Publication:287129
DOI10.1016/S0020-0190(97)00092-6zbMath1336.68131MaRDI QIDQ287129
Publication date: 26 May 2016
Published in: Information Processing Letters (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
Related Items
Semi-on-line bin packing: a short overview and a new lower bound, A robust APTAS for the classical bin packing problem, Batched bin packing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 71/60 theorem for bin packing
- A lower bound for on-line bin packing
- Bin packing can be solved within 1+epsilon in linear time
- Fast algorithms for bin packing
- 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
- Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
- On-line bin packing in linear time