Semi online problems

Gehnen, Matthias; Azar, Yossi; Rossmanith, Peter

doi:10.18154/RWTH-2026-06829

Semi online problems = Semi Online Algorithmen

Gehnen, Matthias^RWTH*

2026

Verantwortlichkeitsangabevorgelegt von Matthias Gehnen, M. Sc.

ImpressumAachen : RWTH Aachen University 2026

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2026

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak09

Hauptberichter/Gutachter
Rossmanith, Peter (Thesis advisor)^RWTH* ; Azar, Yossi (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2026-03-26

Online
DOI: 10.18154/RWTH-2026-06829
URL: https://publications.rwth-aachen.de/record/1038894/files/1038894.pdf

Einrichtungen

Lehr- und Forschungsgebiet Theoretische Informatik (121220)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Stell dir vor, du hast ein beliebiges Problem, für das du eine gute Lösung suchst. Wenn du mit der Situation vertraut bist, weißt, was die Zukunft bringt, welche deine Optionen und deren Konsequenzen sind, dann ist es sicherlich möglich, eine gute Entscheidung zu treffen. In der Realität sind all diese Informationen jedoch nicht immer vorhanden; eine Entscheidung muss dennoch getroffen werden. Glücklicherweise muss man seine Entscheidungen allerdings auch nicht komplett im Dunkeln treffen. Außerdem gibt es häufig die Gelegenheit, Entscheidungen zu revidieren, falls neue Informationen verfügbar sind. In dieser Arbeit werden zwei Ansätze untersucht, die diese Situationen modellieren, und damit zwischen klassischen Offline- und Online-Problemen liegen: Oft kann eine Entscheidung verzögert werden, allerdings häufig nicht umsonst: Beim Buchen gibt es oft die Gelegenheit, statt einer festen Buchung auch eine teurere mit Stornierungsoption zu tätigen. Im Finanzwesen erlauben einem Optionen, zu einem späteren Punkt zu entscheiden, allerdings ist auch dies nicht umsonst. Wir modellieren verschiedene Probleme in diesem Reservierungssetting: Für zwei Varianten des Sekretärinnenproblems, des Simple Knapsack mit Entfernbarkeit sowie des Vertex Cover präsentieren wir optimale Lösungen für alle Reservierungskosten. Für das General Knapsack und allgemeine Knotenlöschungsprobleme wie dem Feedback Vertex Set zeigen wir asymptotische geschlossene Schranken. Noch unrealistischer ist es, anzunehmen, dass eine Entscheidung entweder komplett im Dunkeln (wie bei einem Online-Problem) oder mit allen relevanten Informationen getroffen wird (wie bei einem Offline-Problem): Für gewöhnlich sind nicht alle relevanten Daten verfügbar, man hat aber zumindest eine grobe Idee durch die Erfahrung oder Anwendungen aus dem maschinellen Lernen. Hier kann man annehmen, dass die Größenordnung der Instanz am Anfang bekannt ist, aber die Details erst während der Laufzeit wie bei einem Online-Problem aufgedeckt werden. Auch in diesem Schätzungssetting studieren wir verschiedene Probleme: Für das Simple Knapsack mit und ohne Reservierung und für eingeschränkte Varianten des Bin Packing sowie des Graph Exploration erzielen wir optimale Ergebnisse für jede Güte der Schätzung. Für das Bin Packing sowie das Graph Exploration präsentieren wir obere und untere Schranken. Dazu wird auch eine Studie zum Online Feedback Vertex Set vorgestellt. Überraschenderweise ist diese Arbeit die erste, die dieses natürliche Problem mit interessanter Struktur betrachtet.

Assume you have an arbitrary problem. Likely, you will then try to find a good solution for it. If you are fully aware of the situation, the future, and your options with their consequences, making a good decision is usually possible. However, often you do not have all the necessary information but need to decide anyway. Luckily, this does not imply you need to decide completely in the dark. You also do not have to stick to the decisions made if new information appears. In this thesis, we will discuss two approaches that help to deal with those problems, as they are modeled best between classical offline and online problems: Often, a decision maker is allowed to delay some decisions. In real life, often such options exist, even though it may not for free: If you are considering whether to book something, purchasing some insurance that allows for cancellation might be possible. In finance, buying options allows you to decide at a later point, but again, this does not come for free. In this thesis, various problems are studied within this Reservation Setting: For two variants of the Secretary Problem, the Simple Knapsack with Removability, and the Vertex Cover, we provide matching upper and lower bounds for the whole range of potential reservation costs from zero to expensive. For the General Knapsack and general vertex deletion problems, such as Feedback Vertex Set, we provide asymptotically tight bounds. Assuming that a setting is either in the complete darkness of an online or with full knowledge of an offline problem is probably even more unrealistic: Usually, you might not have all the information available when deciding, but perhaps a rough overview based on experience or machine learning. Even if the necessary data is available, often it is not exact due to e.g., rounding. In those cases, you will likely have this rough overview of the information available from the beginning. More details will likely be available when decisions need to be made, as is known from online problems. Also in this setting, various problems are studied and called a problem with Estimates: For the Simple Knapsack and Simple Knapsack with Removability, as well as for a restricted version of Bin Packing and Graph Exploration, we provide tight bounds for all accuracy factors, and present bounds for Bin Packing and Graph Exploration. Additionally, we present bounds and an algorithm for the Online Feedback Vertex Set. As it is a natural online problem with non-trivial structure, it is surprising that its study is just initiated within this thesis.

OpenAccess:
PDF
(additional files)