+********************************************************************** * * *                                     Einladung * * * *                             Informatik-Oberseminar * * * +**********************************************************************

Zeit: Freitag, 26. August 2022, 13.00 Uhr

Der öffentliche Vortrag findet hybrid statt:

Ort: Raum 9222, Ahornstr. 55

Zoom: https://rwth.zoom.us/j/92249056004?pwd=cHkwRW1lNTlmS1RXQW95Wmw1MjhFQT09

Referent: Janosch Fuchs M.Sc.                 Lehrstuhl Informatik 1

Thema: Graph Exploration with Advice (and Online Crossing Minimization)

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 and 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 an online algorithm. A worst-case analysis 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. 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. 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. In the main part, we analyze the advice complexity of the 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 them 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 a linear amount of advice is sufficient and also necessary to solve the graph exploration problem on directed and undirected graphs.

Es laden ein: die Dozentinnen und Dozenten der Informatik