% 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{Fuchs:853316,
author = {Fuchs, Janosch},
othercontributors = {Unger, Walter and Komm, Dennis and Rossmanith, Peter},
title = {{G}raph exploration with advice and online crossing
minimization},
school = {RWTH Aachen University},
type = {Dissertation},
address = {Aachen},
publisher = {RWTH Aachen University},
reportid = {RWTH-2022-08761},
pages = {1 Online-Ressource : Illustrationen},
year = {2022},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University; Dissertation, RWTH Aachen University, 2022},
abstract = {Online problems reveal their input instance piece by piece
and require an irrevocable decision each time a new piece is
revealed. This scenario models critical applications where a
decision, once it is made, cannot be changed afterwards
which also influences future decisions. Like for classical
offline problems, it is common to make a worst-case analysis
to give a guarantee on the performance of algorithms in this
setting, which are called online algorithms. This is
achieved by assuming that a malicious adversary, knowing the
behavior of the online algorithm, creates the input. Due to
the nature of uncertainty online algorithms rarely compute
an optimal solution. Thus, their performance is measured in
terms of the competitive ratio, which compares the solution
computed by the online algorithm to the optimal solution
achievable when the whole instance is known beforehand. To
measure the impact of the missing knowledge about the future
the classical online setting was extended with a helpful
oracle providing information about the future input. The
online algorithm receives the information by accessing a
tape containing a binary bit string prepared by the oracle.
The number of bits that the algorithm reads during its
computation is called its advice complexity. Bounds on the
advice complexity of an online algorithm that optimally
solves an online problem show how much information about the
future is needed to avoid any mistake. An obvious upper
bound for the advice complexity of all online problems is
the size of the binary encoding of the input instance or the
optimal solution using self-delimiting encoding. But most of
the time it is possible to derive better bounds by encoding
only critical decisions which then reveals the core
difficulty of an online problem. Thus, the advice complexity
strongly correlates to the difficulty of an online problem
and it can be used to measure the difficulty of different
online problems. The first technical part of this thesis
considers an online graph drawing problem on degree-bounded
bipartite graphs, the so-called online slotted One-Sided
Crossing Minimization Problem (online slotted OSCM-$k$). One
set of vertices together with a total ordering is fixed on a
line and known to the online algorithm. In each step a
vertex, which is incident to $k$ vertices of the already
known set, needs to be placed on a free placeholder, which
we call a slot. The slots are also arranged on a line
parallel to the known vertex set. The task is to place the
vertices such that the number of edge crossings is
minimized, when all edges are drawn as straight lines. Note
that the slots make the problem harder to solve for an
online algorithm but in the offline case it is equivalent to
the version without slots. We prove that the online slotted
OSCM-$k$ has no constant competitive ratio. Thus, we look at
the problem on $2$-regular graphs and derive constant upper
and lower bounds for this restricted graph class. The second
part analyzes the advice complexity of a graph exploration
problem. Here, an algorithm has to move an agent through a
graph from vertex to vertex using the edges such that the
agent traverses the cheapest or shortest tour that visits
every vertex at least once. The algorithm does not know the
graph beforehand and each time the agent is located at a new
vertex the reachable neighborhood is revealed together with
the cost to reach all neighboring vertices from the current
location. Already seen or visited vertices are recognizable.
Due to the already known tight upper bound of $n\log(n)$ for
the advice complexity of the graph exploration problem on
dense graphs, we focus on sparse graphs. We show that the
number of advice bits which is sufficient and also necessary
to solve the graph exploration problem on directed and
undirected graphs is linear in the number of edges. We also
investigate how much advice can be saved when the graph
structure is known beforehand and only the traveling cost of
the edges is unknown.},
cin = {121110 / 120000 / 080060},
ddc = {004},
cid = {$I:(DE-82)121110_20140620$ / $I:(DE-82)120000_20140620$ /
$I:(DE-82)080060_20170720$},
typ = {PUB:(DE-HGF)11},
doi = {10.18154/RWTH-2022-08761},
url = {https://publications.rwth-aachen.de/record/853316},
}
guest ::