Robust Online Algorithms for Dynamic Choosing Problems

Sebastian Berndt; Kilian Grage; Klaus Jansen; Lukas Johannsen; Maria Kosche

doi:10.1007/978-3-030-80049-9_4

Robust Online Algorithms for Dynamic Choosing Problems

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

^*Corresponding author for this work

Institute of IT-Security

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.

Original language	English
Title of host publication	Connecting with Computability
Publisher	Springer International Publishing
Publication date	2021
Pages	38-49
DOIs	https://doi.org/10.1007/978-3-030-80049-9_4
Publication status	Published - 2021

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-3-030-80049-9_4

Cite this

@inproceedings{5ca4c7b7dbe14288b8bc5db75f621478,

title = "Robust Online Algorithms for Dynamic Choosing Problems",

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.",

author = "Sebastian Berndt and Kilian Grage and Klaus Jansen and Lukas Johannsen and Maria Kosche",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.",

year = "2021",

doi = "10.1007/978-3-030-80049-9_4",

language = "English",

pages = "38--49",

booktitle = "Connecting with Computability",

publisher = "Springer International Publishing",

}

TY - GEN

T1 - Robust Online Algorithms for Dynamic Choosing Problems

AU - Berndt, Sebastian

AU - Grage, Kilian

AU - Jansen, Klaus

AU - Johannsen, Lukas

AU - Kosche, Maria

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-030-80049-9_4

DO - 10.1007/978-3-030-80049-9_4

M3 - Conference contribution

SP - 38

EP - 49

BT - Connecting with Computability

PB - Springer International Publishing

ER -

Robust Online Algorithms for Dynamic Choosing Problems

Abstract

UN SDGs

Access to Document

Fingerprint

Cite this