Backend
Collective Tree Exploration with Predictions
arXiv cs.MA0 views
arXiv:2611.17482v1 Announce Type: cross Abstract: We study collective tree exploration with subtree-size predictions. In this problem, a team of $k$ mobile agents needs to explore an unknown rooted tree as fast as possible, and whenever a new vertex $u$ is discovered, the team receives a prediction $\hat n_u$ of the number of nodes $n_u$ in the subtree rooted at $u$. We provide algorithmic guarantees under two error measures: the maximum error $E=\max_u|\widehat n_u-n_u|$ and the multiplicative distortion $\mu = (\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 $n$ nodes and depth $D$ in $O(\text{OPT}+E)$ rounds, where $\text{OPT} = \Theta(n/k+D)$ is the offline benchmark, and we show that there is no deterministic algorithm that admits an $O(\text{OPT})+o(E)$ guarantee. For the multiplicative distortion, we present several algorithms that induce a competitive ratio in $\widetilde O(\min\{ \sqrt\mu\log k, \mu\log\log k+\mu^{1.5} \})$, where the $\widetilde O(\cdot)$ may hide logarithmic factors in $\mu$.
Source:https://arxiv.org/abs/2611.17482PreviousPhysical-Risk-Aware Decentralized Agents for Constrained Vehicle CommunicationsNextA Push Down the Mountain: Framing Effects and Internal State Interventions on Collusive Behavior in a Long-Horizon LLM Agent
Related posts
Helsing backer Plural raises $1.1B to fund Europe’s next moonshots
0TechCrunch
Building Mobile Connectivity in Afghanistan: A Look at Roshan
0dev.to
Your Tests Blocked System.exit With a SecurityManager and Java 25 Will Not Let You Install One
0dev.to
We autoscaled our Java pricing service on memory and it grew to twenty pods and stayed there
0dev.to
Nine small tools I stopped installing apps for
0dev.to
I built a small tool to capture website screenshots across devices
0dev.to Productivity