Polylogarithmic Collective Tree Exploration
In the authors' words
We study asynchronous collective tree exploration, where agents with unrestricted communication start at the root of an unknown tree and discover edges online. At each step, an adversary chooses which agent moves. We give a deterministic algorithm that explores any tree with nodes and depth in at most \[ 2n+O\left(k\log^2(k)D\right) \] moves, matching known lower bounds up to a constant factor. As a direct consequence, we obtain a near-optimal competitive ratio of for synchronous collective tree exploration, where all agents move at each round. The proof relies on a multiscale power regularizer that may be of independent interest.
Main resultThe abstract does not state a limitation.
Appeared: Wednesday, September 23. arXiv. Preprint, not yet peer-reviewed.