+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Montag, 13. November 2023, 09.30 Uhr Ort: Informatikzentrum, E3, 2. Etage, Raum 9222 Referent: Henri Lotze M.Sc. Lehr- und Forschungsgebiet Theoretische Informatik Thema: Going Offline -- Delays, Reservations and Predictions in Online Computation Abstract: The study of classical online computation builds upon a rather simple model. The input to a given problem is not known in advance, decisions have to made immediately upon the arrival of a new element and these decisions are irrevocable. 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 a constant approximation ratio in their offline formulation do not admit a 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 Online Simple Knapsack problem and the class of general F-Node- and F-Edge-Deletion problems, the reason for this seems to be that a single, specific bad decision by an algorithm can be arbitrarily punished by an adversary. In this talk, we explore modifications of the classical online model with the aim to find natural models that on the one hand cover a large range of problems and on the other hand work against pathological kinds of instances that restrict an algorithm from obtaining a constant competitive ratio. To this end, we study three modifications of the classical online model. The models that we study are that of "Late Accepts" -- with Advice --, which allows to postpone decisions in online minimization problems until a current partial solution does not uphold a certain property anymore. The second one is that of "Reservations", in which any decision may be postponed for a cost proportional to the gain of an item. Finally, the model of "Bounded Predictions" allows an online algorithm to see the complete instance in advance, with a caveat: There is noise on the instance -- controlled by an adversary -- and each element may actually deviate from its prediction, up to factor that is known to the algorithm. We are able to partially classify the advice complexity of the complete class of both F-Node-Deletion and F-Edge-Deletion problems. We give tight bounds on the competitive ratio for the Online Simple Knapsack problem with Reservations for the whole range of possible reservation costs, i.e. for a factor between 0 and 1. Finally, we give partially tight bounds for the Online Simple Knapsack problem with Bounded Predictions for the whole range of possible noise factors on the size of the items. Es laden ein: die Dozentinnen und Dozenten der Informatik