Fully-Dynamic Bin Packing with Little Repacking

DOI10.4230/LIPIcs.ICALP.2018.51zbMath1499.68411OpenAlexW2962894388MaRDI QIDQ5002726

Björn Feldkord, Guru Prashanth Guruganesh, David Wajc, Anupam Gupta, Amit Kumar, Sören Riechers, Matthias Feldotto

Publication date: 28 July 2021

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9055/pdf/LIPIcs-ICALP-2018-51.pdf/

zbMATH Keywords

tradeoffsbin packingrecoursefully dynamic

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (12)

Online load balancing with general reassignment cost ⋮ Online load balancing on uniform machines with limited migration ⋮ Online minimization of the maximum starting time: migration helps ⋮ The power of amortized recourse for online graph problems ⋮ Online bin covering with limited migration ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Fully dynamic bin packing revisited ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ Online Bin Covering with Limited Migration ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes ⋮ A Robust AFPTAS for Online Bin Packing with Polynomial Migration ⋮ Robust online algorithms for dynamic choosing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New lower bounds for certain classes of bin packing algorithms
• A fundamental restriction on fully dynamic maintenance of bin packing
• A robust APTAS for the classical bin packing problem
• Improved lower bounds for semi-online bin packing problems
• Improved bounds for harmonic-based bin packing algorithms
• On the Lambert \(w\) function
• Fast algorithms for bin packing
• On-line bin packing with restricted repacking
• Algorithms for the Relaxed Online Bin-Packing Model
• Online Scheduling with Bounded Migration
• On the online bin packing problem
• Lower Bound for the Online Bin Packing Problem with Restricted Repacking
• 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
• Improved Space for Bounded-Space, On-Line Bin-Packing
• A Logarithmic Additive Integrality Gap for Bin Packing
• Beating the Harmonic Lower Bound for Online Bin Packing
• On-line bin packing in linear time
• An 8/3 Lower Bound for Online Dynamic Bin Packing
• Fully Dynamic Bin Packing
• A Robust AFPTAS for Online Bin Packing with Polynomial Migration,

This page was built for publication: Fully-Dynamic Bin Packing with Little Repacking