Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs

DOI10.1145/3588437MaRDI QIDQ6075758zbMATH OpenOpenAlexFDO

Authors Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, Andrzej Pelc

Publication date 23 October 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.14916

zbMATH Keywords

graphmobile agenttreasure hunt

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [3] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node $s$. The size of the tank is $B=2(1+alpha)r$, for some positive real constant $alpha$, where $r$, called the radius of the graph, is the maximum distance from $s$ to any other node. The tank of size $B$ allows the agent to make at most $lfloorBfloor$ edge traversals between two consecutive visits at node $s$. Let $e(d)$ be the number of edges whose at least one extremity is at distance less than $d$ from $s$. Awerbuch, Betke, Rivest and Singh [3] conjectured that it is impossible to find a treasure hidden in a node at distance at most $d$ at cost nearly linear in $e(d)$. We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost $mathcalO(e(d)logd)$, and then show how to modify this algorithm to work in the model from [3] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost $Theta(e(d))$ for all graphs and thus our algorithms are also almost optimal.

Recommendations

• On the optimality of a simple strategy for searching graphs
• scientific article; zbMATH DE number 1154599
• An almost-greedy search on random binary vectors and random graphs
• Pebble guided near optimal treasure hunt in anonymous graphs
• Pebble guided optimal treasure hunt in anonymous graphs
• On the optimality of discrete strategies for search on graphs
• Almost discrete search programs on graphs
• Optimal Parametric Search on Graphs of Bounded Tree-Width
• Optimal parametric search on graphs of bounded tree-width

Cites work

• A correction to: ``Agent searching in a tree and the optimality of iterative deepening
• Agent searching in a tree and the optimality of iterative deepening
• Competitive Online Approximation of the Optimal Search Ratio
• Competitive search in symmetric trees
• Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
• Deterministic treasure hunt in the plane with angular hints
• scientific article; zbMATH DE number 7561402 (Why is no real title available?)
• scientific article; zbMATH DE number 6297684 (Why is no real title available?)
• Infinite linear programming and online searching with turn cost
• Lower bounds in on-line geometric searching
• On the linear search problem
• On the two-dimensional cow search problem
• Online algorithms for searching and exploration in the plane
• Online searching with turn cost
• Optimal constrained graph exploration
• Piecemeal graph exploration by a mobile robot.
• Reaching a target in the plane with no information
• Search games: a review
• Searching for an axis-parallel shoreline
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• Searching in the plane
• The theory of search games and rendezvous.
• The ultimate strategy to search on \(m\) rays?
• Treasure hunt with advice
• Yet more on the linear search problem

Cited in

(6)

• Pebble guided near optimal treasure hunt in anonymous graphs
• Pebble guided optimal treasure hunt in anonymous graphs
• scientific article; zbMATH DE number 7561402 (Why is no real title available?)
• Impact of knowledge on the cost of treasure hunt in trees
• Deterministic treasure hunt and rendezvous in arbitrary connected graphs
• On time-travel planning in dynamic graphs

This page was built for publication: Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075758)