% IMPORTANT: The following is UTF-8 encoded. This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.
@PHDTHESIS{Lotze:974660,
author = {Lotze, Henri},
othercontributors = {Rossmanith, Peter and Boyar, Joan},
title = {{G}oing offline - delays, reservations and predictions in
online computation},
school = {RWTH Aachen University},
type = {Dissertation},
address = {Aachen},
publisher = {RWTH Aachen University},
reportid = {RWTH-2023-11519},
pages = {1 Online-Ressource : Illustrationen},
year = {2023},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University 2024; Dissertation, RWTH Aachen University, 2023},
abstract = {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.},
cin = {121220 / 120000},
ddc = {004},
cid = {$I:(DE-82)121220_20140620$ / $I:(DE-82)120000_20140620$},
typ = {PUB:(DE-HGF)11},
doi = {10.18154/RWTH-2023-11519},
url = {https://publications.rwth-aachen.de/record/974660},
}
guest ::