+**********************************************************************
*
*
* 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
