| 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 trade-off 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.
|
|---|