Online bin covering with limited migration

DOI10.1016/j.jcss.2023.01.001OpenAlexW2980030576MaRDI QIDQ2689369

Lars Rohwedder, Marten Maack, Klaus Jansen, Asaf Levin, Sebastian Berndt, Leah Epstein

Publication date: 10 March 2023

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2023.01.001

zbMATH Keywords

bin coveringworst-case analysismigration factor

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online bin covering: expectations vs. guarantees
• Robust algorithms for preemptive scheduling
• Class constrained bin covering
• A robust APTAS for the classical bin packing problem
• Online algorithms for a dual version of bin packing
• Optimal on-line algorithms for variable-sized bin covering
• An asymptotic fully polynomial time approximation scheme for bin covering.
• Online variable sized covering
• Probabilistic analysis of online (class-constrained) bin packing and bin covering
• Comparing online algorithms for bin packing problems
• Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering
• Robust Approximation Schemes for Cube Packing
• Online Scheduling with Bounded Migration
• Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures
• On a dual version of the one-dimensional bin packing problem
• Handbook of Approximation Algorithms and Metaheuristics
• Fully-Dynamic Bin Packing with Little Repacking
• Symmetry exploitation for online machine covering with bounded migration
• A Robust AFPTAS for Online Bin Packing with Polynomial Migration,
• Lower bounds for several online variants of bin packing