Metraipolis › archive › dc_9293ceacb13e
Online Treasure Hunt in Vertex-Permuted Dynamic Rings — arXiv:2609.11013
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.11013
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T05:44:49.539Z
- SHA-256 of the archived text
41e67989e12a7364acaf9e3b9dc919a13f6bef0aa2030f2474380d649d277eac- Stable URL of this page
https://metraipolis.com/documento/dc_9293ceacb13e
How to cite
Online Treasure Hunt in Vertex-Permuted Dynamic Rings — arXiv:2609.11013 — arXiv (en), https://arxiv.org/abs/2609.11013 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9293ceacb13e (Metraipolis archive dc_9293ceacb13e, sha256 41e67989e12a7364acaf9e3b9dc919a13f6bef0aa2030f2474380d649d277eac)
BibTeX
@misc{dc9293ceacb13e,
title = {Online Treasure Hunt in Vertex-Permuted Dynamic Rings — arXiv:2609.11013},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.11013},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9293ceacb13e; sha256 41e67989e12a7364acaf9e3b9dc919a13f6bef0aa2030f2474380d649d277eac},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.11013. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the problem of treasure hunt by a group of $k \geq 1$ agents in vertex-permuted dynamic rings (VP). In this model, the $n$ vertices remain on a ring but are permuted at each time step. We first show that treasure hunt is impossible for any $k \leq n-3$ agents, if there are no restrictions on the sequence of permutations used in the dynamic ring. We then study the $VP(\delta)$ setting, in which for every pair $i, j$ of vertices, the edge $(i, j)$ is guaranteed to appear within $\delta$ steps. We show that the class $VP(\delta)$ is feasible only for $\delta \geq \left\lceil \frac{n-1}{2}\right\rceil$. For the one-agent case, we show a tight bound of $\Theta(\delta n)$ on the worst-case search time as well as competitive ratio of any online algorithm for treasure hunt, provided $\delta \geq 2n$. We then give an optimal algorithm for $k$ agents, thereby showing that $k$ agents can obtain a speedup of $k$ on the worst-case search time. Finally, in the R-VP setting, in which in every step, the vertices are arranged as a ring according to a random permutation, we show that treasure hunt takes expected $\Theta(n)$ steps against an oblivious adversary and $\Theta(n \log n)$ steps against an adaptive adversary.
Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-11 in cs.DC).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.11013 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T05:26:44.590Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).