Treasure Hunt with Advice

DOI10.1007/978-3-319-25258-2_23zbMath1471.68095OpenAlexW2240416680MaRDI QIDQ3460725

Richard Královič, Dennis Komm, Jasmin Smula, Rastislav Královič

Publication date: 8 January 2016

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-25258-2_23

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Communication complexity, information complexity (68Q11)

Related Items

Lower and upper competitive bounds for online directed graph exploration ⋮ Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs ⋮ Impact of knowledge on the cost of treasure hunt in trees ⋮ Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs ⋮ Advice complexity of adaptive priority algorithms ⋮ Online search with a hint ⋮ Deterministic treasure hunt in the plane with angular hints ⋮ Wireless evacuation on \(m\) rays with \(k\) searchers ⋮ Online Minimum Spanning Tree with Advice ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Exploring sparse graphs with advice

Cites Work

• Unnamed Item
• Online algorithms for searching and exploration in the plane
• Online computation with advice
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• Searching in the plane
• The string guessing problem as a method to prove lower bounds on the advice complexity
• Shortest paths without a map
• Communication algorithms with advice
• Constructing competitive tours from local information
• Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences
• On Advice Complexity of the k-server Problem under Sparse Metrics
• On the Advice Complexity of the Knapsack Problem
• On Online Algorithms with Advice for the k-Server Problem
• Online Graph Exploration with Advice
• Collaborative search on the plane without communication
• On the Advice Complexity of the k-Server Problem
• Information Complexity of Online Problems
• On the Advice Complexity of Online Problems
• A Separator Theorem for Planar Graphs
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Competitive Algorithms for Layered Graph Traversal
• Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology
• Oracle size
• Measuring the problem-relevant information in input