← 研踪 PaperTrailarXiv:2611.17482 · v1
Collective Tree Exploration with Predictions
首次提交 2026-11-13 04:12
版本更新 2026-11-13 04:12
雷达观测 2026-11-17 04:58
摘要
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 .
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 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 .
查看此版本解读 →查看此版本原文 ↗