Navigating in Trees with Permanently Noisy Advice
| Autor: | Lucas Boczkowski, Amos Korman, Uriel Feige, Yoav Rodeh |
|---|---|
| Přispěvatelé: | Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Weizmann Institute of Science [Rehovot, Israël], European Project: 648032,H2020,ERC-2014-CoG,DBA(2015), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Polynomial
Data structures Average Case Analysis Node (networking) [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Permanents Faults 0102 computer and information sciences 02 engineering and technology Expected value Graph search 01 natural sciences Tree (graph theory) Combinatorics [INFO.INFO-MC]Computer Science [cs]/Mobile Computing Mathematics (miscellaneous) 010201 computation theory & mathematics Search algorithm 0202 electrical engineering electronic engineering information engineering Search problem 020201 artificial intelligence & image processing Treasure Advice (complexity) Mathematics |
| Zdroj: | ACM Transactions on Algorithms ACM Transactions on Algorithms, Association for Computing Machinery, 2021, Leibniz International Proceedings in Informatics (LIPIcs), pp.1-32. ⟨10.1145/3448305⟩ ACM Transactions on Algorithms, 2021, Leibniz International Proceedings in Informatics (LIPIcs), pp.1-32. ⟨10.1145/3448305⟩ |
| ISSN: | 1549-6325 |
| DOI: | 10.1145/3448305⟩ |
| Popis: | We consider a search problem on trees in which an agent starts at the root of a tree and aims to locate an adversarially placed treasure, by moving along the edges, while relying on local, partial information. Specifically, each node in the tree holds a pointer to one of its neighbors, termed advice . A node is faulty with probability q . The advice at a non-faulty node points to the neighbor that is closer to the treasure, and the advice at a faulty node points to a uniformly random neighbor. Crucially, the advice is permanent , in the sense that querying the same node again would yield the same answer. Let Δ denote the maximum degree. For the expected number of moves (edge traversals) until finding the treasure, we show that a phase transition occurs when the noise parameter q is roughly 1 √Δ. Below the threshold, there exists an algorithm with expected number of moves O ( D √Δ), where D is the depth of the treasure, whereas above the threshold, every search algorithm has an expected number of moves, which is both exponential in D and polynomial in the number of nodes n . In contrast, if we require to find the treasure with probability at least 1 − δ, then for every fixed ɛ > 0, if q < 1/Δ ɛ , then there exists a search strategy that with probability 1 − δ finds the treasure using (Δ −1 D ) O (1/ε) moves. Moreover, we show that (Δ −1 D ) Ω(1/ε) moves are necessary. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|