Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps

DOI10.1137/S0097539794276749MaRDI QIDQ4210166zbMATH OpenFDO

Authors Zoran Ivković, Errol L. Lloyd

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

bin packingfully dynamic algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Data structures (68P05) Parallel algorithms in computer science (68W10)

Recommendations

• Fully Dynamic Bin Packing
• A fundamental restriction on fully dynamic maintenance of bin packing
• Fully dynamic bin packing revisited
• scientific article; zbMATH DE number 6767525
• Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time

Cites work

• A 71/60 theorem for bin packing
• A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
• 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
• New Algorithms for Bin Packing
• On-line bin packing in linear time
• Parallel approximation algorithms for bin packing
• Reducibility among combinatorial problems
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(19)

• Semi-on-line bin packing: a short overview and a new lower bound
• A fundamental restriction on fully dynamic maintenance of bin packing
• A survey on combinatorial optimization in dynamic environments
• Dynamic windows scheduling with reallocation
• Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time
• scientific article; zbMATH DE number 6767525 (Why is no real title available?)
• A robust AFPTAS for online bin packing with polynomial migration
• On dynamic bin packing: An improved lower bound and resource augmentation analysis
• Fully dynamic maintenance of vertex cover
• Resource augmented semi-online bounded space bin packing
• A robust APTAS for the classical bin packing problem
• Improved lower bounds for semi-online bin packing problems
• Fully-dynamic bin packing with little repacking
• Dynamic bin packing with unit fraction items revisited
• Batched bin packing
• Fully dynamic bin packing revisited
• Fully Dynamic Bin Packing
• Dynamic bin packing of unit fractions items
• On-line bin packing with restricted repacking

This page was built for publication: Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps

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