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

Dreame X50 Ultra: designing a Shopify buying journey around fit, bundles and payment conditions
0dev.to JavaScript
Connect Four in 86 lines: how I coded the rules for a multiplayer browser game
0dev.to JavaScript
From Prompt to Production: Architectural Deep‑Dive into MIT’s “How to Make Almost Anything” Framework
0dev.to Rust
PRISM: Preference-based Reward and Uncertainty-Integrated Synthesis Minimization for RTL PPA Optimization
0arXiv cs.SE
The $\alpha$-Limit Problem: Convergence of a Linear Degenerate Interface Transmission Problem
0arXiv cs.NA
A Spectral Proximal DC Algorithm with Nonmonotone Line Search and Extrapolation
0arXiv cs.NA