Going offline - delays, reservations and predictions in online computation

Lotze, Henri; Rossmanith, Peter; Boyar, Joan

doi:42796

Going offline - delays, reservations and predictions in online computation

Lotze, Henri^RWTH*

2023 & 2024

Verantwortlichkeitsangabevorgelegt von Henri Lotze, M.Sc.

ImpressumAachen : RWTH Aachen University 2023

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2023

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2024

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Rossmanith, Peter (Thesis advisor)^RWTH* ; Boyar, Joan (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2023-11-13

Online
DOI: 10.18154/RWTH-2023-11519
URL: https://publications.rwth-aachen.de/record/974660/files/974660.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
advice complexity (frei) ; late accept model (frei) ; machine learned advice (frei) ; online algorithms (frei) ; online computation (frei) ; reservation costs (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Die Forschung zu Online-Algorithmen basiert auf einem recht simplen Modell. Die Eingabe für ein gegebenes Problem ist zu Anfang nicht bekannt und wird erst Stück für Stück aufgedeckt, woraufhin ein Algorithmus unmittelbar und unwiderruflich Entscheidungen treffen muss, z.B. ob ein Element der Eingabe in seine Lösungsmenge aufgenommen werden soll oder nicht. Während dieses Modell sehr gut dazu geeignet ist um worst-case-Schranken für eine große Breite von Problemen zu berechnen, gibt es einige Probleme, die sich nicht gut für diese Art von Analyse eignen. Selbstverständlich sind Probleme, die bereits in ihrer Offline-Formulierung keine konstante Approximationsrateerlauben auch in ihrer Online-Formulierung nicht durch eine konstante Kompetitivitätsrate abschätzbar. Es gibt jedoch einige Probleme, welche zwar approximierbar sind, jedoch keine konstante Kompetitivitätsrate in ihrer Online-Formulierung erlauben. Für eine Teilmenge dieser Probleme, wie das Simple Knapsack-und das Vertex Cover-Problem --- und deren Generalisierungen ---, scheint der Grund für dieses Verhalten in einzelnen, sehr spezifischen, schlechten Entscheidungen eines Algorithmuses zu liegen, welche ein böser Gegenspieler willkürlich ausnutzen und bestrafen kann. Es gibt bereits eine große Menge an Forschung dazu, wie man entweder die Probleme selber oder das Online-Modell als Ganzes modifizieren kann um die Leistungsfähigkeit von Algorithmen unter diesen zu untersuchen. Ein Problem mit vielen dieser Formulierungen ist, dass diese sehr problemspezifisch formuliert sind. Für das Knapsack-Problem etwa sind beliebte Modifikationen das hinzufügen von zusätzlichen Behältern, die Adjustierung der Rucksackgröße durch das Verfahren der resource augmentation oder die Möglichkeit, Elements aus einem Rucksack wieder zu entfernen. Alleine die letzte Modifikation lässt sich einfach auf andere Probleme transferieren. In dieser Dissertation erkunden wir Modifikationen des klassischen Online-Modells mit dem Ziel, dabei möglichst natürliche Modelle zu finden, welche einerseits auf eine breite Masse an Problemen angewandt werden können und sich andererseits gegen pathologische Arten von Instanzen wenden, welche einen Algorithmus davon abhalten, eine konstante Schranke auf seine Kompetitivitätsrate zu erhalten. Zu diesem Zwecke untersuchen wir drei Modifikationen des klassischen Online-Modells. Die erste dieser Modifikationen ist die der delayed decisions, welche zuerst von Boyar et al. als das late accept-Modelleingeführt wurden. Dieses kann auf Probleme angewandt werden, in welchen ein neu präsentiertes Element der Eingabe nicht die bisherige Zwischenlösung eines Algorithmuses invalidiert oder auf anderem Wege eine unmittelbare Entscheidung verlangt. Die Familie von Problemen, die wir nach diesem Modell analysieren, hauptsächlich mit advice, ist die der Knoten- und Kanten-Löschungsprobleme bedingt durch eine beschränkte Menge F von verbotenen Graphen. Wir zeigen, dassabhängig von der verbotenen Menge, die advice-Komplexität für dieses Modell zwischen linearem und überhaupt keinem advice in der Größe der optimalen Lösung nötig ist, um das Problem optimal zu lösen. Die zweite Modifikation ist die der reservation costs, bei der ein Preis in Abhängigkeit von dem Maß an Qualität gezahlt werden kann, die ein Element für einen Algorithmus hat, wenn dieses aufgedeckt wird. Die Entscheidung, was dann mit diesem Element geschehen soll ---üblicherweise ob es zur Lösungsmenge hinzugefügt werden soll oderabgelehnt wird --- darf in diesem Fall bis zum Ende der gesamten Instanz herausgezögert werden. Wir untersuchen das Simple Knapsack-Problem, in dem die Kosten einer Reservierung ein festgelegter Anteil der Größe eines Elements ist. Wir zeigen, dass die Kompetitivitätsrate für solch einen proportionalen Kostenfaktor alpha zwischen 0 und 1 durch eine von insgesamt vier Funktionssegmenten beschrieben werden kann, abhängig vom konkreten Wert von alpha. Diese Modifikation lässt sich sehr natürlich auf Probleme anwenden, in denen jedem Element der Eingabe ein Gewinn zugeordnet ist, lässt sich jedoch recht einfach verallgemeiern, wenn ein Kostemaß bedacht gewählt wird. Zuletzt analysieren wir eine Modifikation von relativen Fehlern auf einer Instanz, welche wir bounded predictions nennen. In diesem Modell ist die gesamte Instanz im vorhinein bekannt. Jedoch kann jedes anschließend aufgedeckte Element der Instanz um einen Faktor, welche dem Algorithmus bekannt ist, von seiner angekündigten Größe abweichen. Auch unter dieser Modifikation untersuchen wir das Simple Knapsack-Problem, mit dem Ergebnis, dass eine konstant beschränkte Kompetitivitätsrate bis zu einem relativen Fehlerfaktor von 1 erreicht werden kann. Die Funktion der Kompetitivitätsrate abhängig von dem erlaubten Grad des Fehlers verhält sich eigenartig, indem drei alternierende Strategien periodisch dominieren.

The study of classical online computation builds upon a rather simple model. The input to a given problem is not known in advance and is revealed element by element, to which an algorithm is supposed to outputan immediate and final decision, e.g. whether to add an element to its solution set or not. While this model is very well suitable to compute worst case bounds to a broad range of problems, there are some problems which are not well suited for this analysis. Naturally, problems that do not admit aconstant approximation ratio in their offline formulation do not admita constant competitive ratio in the worst case in the online formulation. However, some problems that are approximable still do not admit a constant competitive ratio when analyzed in the online case. For a subset of these problems, such as the Simple Knapsack or Vertex Coverproblem --- and their generalizations ---, the reason for this seems to be that a single, specific bad decision by an algorithm can be arbitrarily punished by an adversary. There has been extensive research for such problems on how to modifyeither the set of problem instances or the online model itself and to study the performance of algorithms under such modified models and problems. An issue with many of these modifications is that they arevery specific to a given problem. For example, popular modificationsto the Knapsack problem are adding additional bins, adjusting the size ofthe knapsack of the algorithm by resource augmentation or to allow forthe removal of items. Arguably, only the last modification is easily transferable to other problems. In this thesis, we explore modifications of the classical online model with the aim to find natural models that cover a large range of problems and on the other hand work against pathological kinds ofinstances that restrict an algorithm from obtaining a constant competitive ratio. To this end, we study three modifications of the classical online model. The first modification that we call delayed decision was first described by Boyar et al. as the late accept model. It can be applied to problems in which a newly presented element of the instance does not invalidate the current intermediate solution of the online algorithm or otherwise warrants an immediate decision. The family of problems that we analyze under this model, mostly with advice, is thatof node- and edge-deletion problems under some finite obstruction setF. We find that, depending on the obstruction set, the advice complexity for this model varies between advice linear in the size of the optimal solution, to no advice being needed to optimally solve such a deletion problem. The second modification is that of reservation costs, in which a cost in regards to the measure of quality of an item for analgorithm can be paid when a new element is revealed. The decision on what to do with this item --- commonly whether to add it to thesolution set or to discard it --- may then be delayed up to the end of the instance. We analyze the Simple Knapsack problem where the cost of reservation is a fixed fraction of the size of the reserved item. We find that for such a proportional cost factor alpha between 0 and1, the competitive ratio is described by one of four function segments, depending on the concrete value of alpha under which the problem is analyzed. This modification is naturally applicable to problems where each item is associated with a gain, but generalizes quite broadly if one defines a sensible measure of cost. Finally, we analyze a modification of a relativean instance, which we name bounded predictions. In thissetting, the complete instance is announced before hand. However, anyelement that is revealed may deviate from its announcement by a factor, which is known to the algorithm. Again, we analyze the Simple Knapsack problem under this modification, finding that aconstant competitive ratio can be achieved for a relative error smaller than one. The resulting function of the competitive ratio depending on the allowed margin of error behave scuriously, with alternating strategies dominating in a periodic fashion.

OpenAccess:
PDF
(additional files)