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

DOI10.1016/S0020-0190(97)00092-6zbMATH Open1336.68131OpenAlexW1493845713MaRDI QIDQ287129FDOQ287129

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

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
• scientific article; zbMATH DE number 6767525
• 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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A 71/60 theorem for bin packing
• Bin packing can be solved within 1+epsilon in linear time
• A simple on-line bin-packing algorithm
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• A lower bound for on-line bin packing
• Fast algorithms for bin packing
• Analysis of a Compound Bin Packing Algorithm
• Title not available (Why is that?)
• Dynamic Bin Packing
• New Algorithms for Bin Packing
• Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
• On-line bin packing in linear time

Cited In (6)

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

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)