Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time

DOI10.1016/S0020-0190(97)00092-6zbMath1336.68131MaRDI QIDQ287129

Zoran Ivković, Errol L. Lloyd

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00092-6

zbMATH Keywords

computational complexity; bin packing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

A Robust AFPTAS for Online Bin Packing with Polynomial Migration, 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, Fully dynamic bin packing revisited

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