guest ::
%0 Thesis %A Lotze, Henri %T Going offline - delays, reservations and predictions in online computation %I RWTH Aachen University %V Dissertation %C Aachen %M RWTH-2023-11519 %P 1 Online-Ressource : Illustrationen %D 2023 %Z Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2024 %Z Dissertation, RWTH Aachen University, 2023 %X 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. %F PUB:(DE-HGF)11 %9 Dissertation / PhD Thesis %R 10.18154/RWTH-2023-11519 %U https://publications.rwth-aachen.de/record/974660