WorksComputer Science
Collective Tree Exploration with Predictions
Abstract
We study collective tree exploration with subtree-size predictions. In this problem, a team of mobile agents needs to explore an unknown rooted tree as fast as possible, and whenever a new vertex is discovered, the team receives a prediction of the number of nodes in the subtree rooted at . We provide algorithmic guarantees under two error measures: the maximum error and the multiplicative distortion . For the maximum error, we present a deterministic algorithm that explores any tree with nodes and depth in rounds, where is the offline benchmark, and we show that there is no deterministic algorithm that admits an guarantee. For the multiplicative distortion, we present several algorithms that induce a competitive ratio in , where the may hide logarithmic factors in .