Special Online Problems with AdviceCopyright: Lukas Netz
Online algorithms compute solutions for problems without knowing the future input. The lack of information prohibits to compute optimal solutions. To measure the quality of an online algorithm the competitive ratio, e.g., the ratio between the optimal solution and the computed solution, was introduced. The best possible competitive ratios for different online problems can be used to compare the difficulty of online problems.
But some problems have no constant competitive ratio, which makes a comparison impossible. Therefore, advice complexity was introduced to extend the online setting. Here, the algorithm has access to an advice tape which was written by a helpful oracle. Reading information from the tape generates costs but also provides information to help computing a solution. The number of needed bits until the computation is finished is called the advice complexity of an algorithm. It represents the amount of missing crucial information for an online problem. This parameter allows to compare different online problems by their number of needed advice bits.
There are two different approaches for using the advice. The advice can be used to compute an optimal solution in an online scenario or it can be used to achieve a constant competitive ratio. In the latter case, a trade off between advice bits and the best achievable competitive ratio with advice is studied.
The aim of my work is to find new lower and upper bounds for the advice complexity for graph theoretical problems, like Graph Exploration. In the graph exploration problem, an algorithm has to decide how the agent, also called explorer, moves through a network such that every point of interest is visited at least once. The best known upper bound to compute an optimal solution is n log(n) bits of advice. The idea of this approach is to enumerate the vertices in the order in which the explorer will visit them for the first time. In my thesis I show that there is an online algorithm with an advice complexity linear in the number of edges of the graph. For graphs with an outgoing degree of at most two, the advice complexity is linear in the number of vertices.