Janosch Fuchs: Special Online Problems with Advice
Janosch Fuchs is working on the graph exploration problem, an online variation of the classic (offline) Hamilton Cycle and Hamilton Path problem, that (in contrast to the offline version) allows multiple visits to the same vertex. In other words, an online decision maker has to move through a graph with vertices and edges such that every point of interest is seen and visited at least once. The knowledge of the decision maker is limited by his physical perception capacities. In the so-called fixed-graph scenario, the decision maker perceives all reachable vertices, their unique names and their distance from the current position; there is unlimited memory, and the decision maker recognizes if he has already seen a vertex before. Fuchs discusses the advice complexity of the graph exploration problem, which denotes the number of bits providing additional information about the structure of the future input that the decision maker needs in order to compute an offline-optimal solution in the online setting. Hence, the advice complexity is a way to measure the impact of uncertainty in online problems. Fuchs concentrates on the analysis of various graph classes and provides matching or almost matching upper and lower bounds on the advice complexity. For sparse graphs, the derived bounds are linear in the number of vertices.