跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.17482 · v1

Collective Tree Exploration with Predictions

首次提交 2026-11-13 04:12
版本更新 2026-11-13 04:12
雷达观测 2026-11-17 04:58
arXiv ↗PDF ↗

摘要

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 μμ.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-13 04:12 · 最新观测版本

Collective Tree Exploration with Predictions

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 μμ.

查看此版本解读 →查看此版本原文 ↗