Meno:  Peter


Priezvisko:  Fulla


Názov:  Advice Complexity of Online Algorithms


Vedúci:  prof. RNDr. Rastislav Královič, PhD.


Rok:  2014


Blok:  INF


Kµúčové slová:  online graph exploration, competitive analysis, advice complexity, online algorithms


Abstrakt:  In the online graph exploration problem, an agent explores an unknown weighted graph aiming to visit each vertex at least once and return to the starting node while minimizing the total cost of its walk. The topology of the graph is revealed to the agent gradually: After visiting a node, the agent learns all edges incident to it. We provide some additional information about the input to the agent in the form of advice, and study the tradeoff between the amount of provided advice and the competitive ratio (with respect to an optimal offline algorithm knowing the graph beforehand). In this thesis, we focus on the exploration problem on two restricted classes of graphs. We give asymptotically tight bounds of Theta(lg n) and Theta(n lg n) on advice necessary to yield an optimal solution on cycles and unweighted graphs respectively. Furthermore, we propose a new algorithm that explores cycles achieving the competitive ratio of 1 + 3/2^(2^k) (for any constant k) while requiring advice of size O(k) bits. Finally, we provide a lower bound of Omega(n) on advice necessary to achieve a competitive ratio better than 1 + 1/(ln 16  1) = 1.564 on unweighted graphs.

