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

DOI10.1016/S0020-0190(97)00092-6zbMath1336.68131OpenAlexW1493845713MaRDI 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 complexitybin packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (5)

Semi-on-line bin packing: a short overview and a new lower bound ⋮ Batched bin packing ⋮ Fully dynamic bin packing revisited ⋮ A robust APTAS for the classical bin packing problem ⋮ A Robust AFPTAS for Online Bin Packing with Polynomial Migration

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

This page was built for publication: Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time