Robust Online Algorithms for Dynamic Choosing Problems

Sebastian Berndt, Kilian Grage*, Klaus Jansen, Lukas Johannsen, Maria Kosche

*Korrespondierende/r Autor/-in für diese Arbeit

Abstract

Semi-online algorithms that are allowed to perform a bounded amount of repacking achieve guaranteed good worst-case behaviour in a more realistic setting. Most of the previous works focused on minimization problems that aim to minimize some costs. In this work, we study maximization problems that aim to maximize their profit.

We mostly focus on a class of problems that we call choosing problems, where a maximum profit subset of a set objects has to be maintained. Many known problems, such as Knapsack, MaximumIndependentSet and variations of these, are part of this class. We present a framework for choosing problems that allows us to transfer offline α
-approximation algorithms into (α−ϵ)-competitive semi-online algorithms with amortized migration O(1/ϵ). Moreover we complement these positive results with lower bounds that show that our results are tight in the sense that no amortized migration of o(1/ϵ) is possible.
OriginalspracheEnglisch
TitelConnecting with Computability
Herausgeber (Verlag)Springer International Publishing
Erscheinungsdatum2021
Seiten38-49
DOIs
PublikationsstatusVeröffentlicht - 2021

Fingerprint

Untersuchen Sie die Forschungsthemen von „Robust Online Algorithms for Dynamic Choosing Problems“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitieren