Robust Online Algorithms for Certain Dynamic Packing Problems

Sebastian Berndt, Valentin Dreismann, Kilian Grage*, Klaus Jansen, Ingmar Knof

*Corresponding author for this work


Online algorithms that allow a small amount of migration or recourse have been intensively studied in the last years. They are essential in the design of competitive algorithms for dynamic problems, where objects can also depart from the instance. In this work, we give a general framework to obtain so called robust online algorithms for a variety of dynamic problems: these online algorithms achieve an asymptotic competitive ratio of +\epsilon with migration, where is the best known offline asymptotic approximation ratio. For our framework, we require only two ingredients: (i) the existence of an online algorithm for the static case (without departures) that provides a provably good solution compared to the total volume of the instance and (ii) that the optimal solution always exceeds this total volume. If these criteria are met, we can complement the online algorithm with any offline algorithm. While these criteria are naturally fulfilled by many dynamic problems, they are especially suited for packing problems. In order to show the usefulness of our approach in this area, we improve upon the best known robust algorithms for the dynamic versions of generalizations of Strip Packing and Bin Packing, including the first robust algorithms for general d-dimensional Bin Packing and Vector Packing.

Original languageEnglish
Title of host publicationWAOA 2019: Approximation and Online Algorithms
EditorsEvripidis Bampis, Nicole Megow
Number of pages17
Volume11926 LNCS
PublisherSpringer, Cham
Publication date25.01.2020
ISBN (Print)978-3-030-39478-3
ISBN (Electronic)978-3-030-39479-0
Publication statusPublished - 25.01.2020
Event17th International Workshop on Approximation and Online Algorithms
- Munich, Germany
Duration: 12.09.201913.09.2019
Conference number: 236729


Dive into the research topics of 'Robust Online Algorithms for Certain Dynamic Packing Problems'. Together they form a unique fingerprint.

Cite this