Online graph exploration with advice
Date
2012Sujet
Résumé
We study the problem of exploring an unknown undirected graph with non-negative edge weights. Starting at a distinguished initial vertex s, an agent must visit every vertex of the graph and return to s. Upon visiting a node, the agent learns all incident edges, their weights and endpoints. The goal is to find a tour with minimal cost of traversed edges. This variant of the exploration problem has been introduced by Kalyanasundaram and Pruhs in [18] and is known as a fixed graph scenario. There have been recent advances by Megow, Mehlhorn, and Schweitzer ([19]), however the main question whether there exists a deterministic algorithm with constant competitive ratio (w.r.t. to offline algorithm knowing the graph) working on all graphs and with arbitrary edge weights remains open. In this paper we study this problem in the context of advice complexity, investigating the tradeoff between the amount of advice available to the deterministic agent, and the quality of the solution. We show that Ω(n logn) bits of advice are necessary to achieve a competitive ratio of 1 (w.r.t. an optimal algorithm knowing the graph topology). Furthermore, we give a deterministic algorithm which uses O(n) bits of advice and achieves a constant competitive ratio on any graph with arbitrary weights. Finally, going back to the original problem, we prove a lower bound of 5/2 - ε for deterministic algorithms working with no advice, improving the best previous lower bound of 2 - ε of Miyazaki, Morimoto, and Okabe from [20]. In this case, significantly more elaborate technique was needed to achieve the result. © 2012 Springer-Verlag.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Knowledge distillation on neural networks for evolving graphs
Antaris S., Rafailidis D., Girdzijauskas S. (2021)Graph representation learning on dynamic graphs has become an important task on several real-world applications, such as recommender systems, email spam detection, and so on. To efficiently capture the evolution of a graph, ... -
Different speeds suffice for rendezvous of two agents on arbitrary graphs
Kranakis E., Krizanc D., Markou E., Pagourtzis A., Ramírez F. (2017)We consider the rendezvous problem for two robots on an arbitrary connected graph with n vertices and all its edges of length one. Two robots are initially located on two different vertices of the graph and can traverse ... -
GRATIS: A GRaph tool for information systems scientists
Vlachos V., Siklafidis T., Chantzi K. (2019)All technological, biological and social networks can be represented as graphs. Therefore, graphs are utilised in simulation-based studies of new algorithms and protocols in various scientific fields. This paper presents ...