betaFeedback

WorksComputer Science

Collective Tree Exploration with Predictions

Abstract

We study collective tree exploration with subtree-size predictions. In this problem, a team of kk mobile agents needs to explore an unknown rooted tree as fast as possible, and whenever a new vertex uu is discovered, the team receives a prediction n^u\hat n_u of the number of nodes nun_u in the subtree rooted at uu. We provide algorithmic guarantees under two error measures: the maximum error E=max⁡u∣n^u−nu∣E=\max_u|\widehat n_u-n_u| and the multiplicative distortion μ=(max⁡un^u/nu)(max⁡unu/n^u)μ= (\max_u\widehat n_u/n_u)(\max_u n_u/\widehat n_u). For the maximum error, we present a deterministic algorithm that explores any tree with nn nodes and depth DD in O(OPT+E)O(\text{OPT}+E) rounds, where OPT=Θ(n/k+D)\text{OPT} = Θ(n/k+D) is the offline benchmark, and we show that there is no deterministic algorithm that admits an O(OPT)+o(E)O(\text{OPT})+o(E) guarantee. For the multiplicative distortion, we present several algorithms that induce a competitive ratio in O~(min⁡{μlog⁡k,μlog⁡log⁡k+μ1.5})\widetilde O(\min\{ \sqrtμ\log k, μ\log\log k+μ^{1.5} \}), where the O~(⋅)\widetilde O(\cdot) may hide logarithmic factors in μμ.

Paper details

vlnc:W_vht68e7n
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…