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

DOI10.1016/S0020-0190(97)00092-6zbMATHOpenAlexMaRDI QIDQ287129FDO

Authors 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

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

Recommendations

• Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
• A sublinear-time approximation scheme for bin packing
• On dynamic bin packing: An improved lower bound and resource augmentation analysis
• On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis
• A dense hierarchy of sublinear time approximation schemes for bin packing
• Fully dynamic bin packing revisited
• Publication:5351895
• Fully-dynamic bin packing with little repacking
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• An \(\frac{8}{3}\) lower bound for online dynamic bin packing

Cites work

• scientific article; zbMATH DE number 3890754 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A 71/60 theorem for bin packing
• A lower bound for on-line bin packing
• A simple on-line bin-packing algorithm
• Analysis of a Compound Bin Packing Algorithm
• Bin packing can be solved within 1+epsilon in linear time
• Dynamic Bin Packing
• Fast algorithms for bin packing
• Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
• New Algorithms for Bin Packing
• On-line bin packing in linear time
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(6)

• Semi-on-line bin packing: a short overview and a new lower bound
• Fully dynamic bin packing revisited
• Batched bin packing
• A robust APTAS for the classical bin packing problem
• Fully Dynamic Bin Packing
• A robust AFPTAS for online bin packing with polynomial migration

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287129)