text: In rendezvous, two agents traverse network edges in synchronous rounds and have to meet at some node. In treasure hunt, a single agent has to find a stationary target situated at an unknown node of the network. We study tradeoffs between the amount of information ( @math ) available @math to the agents and the cost (number of edge traversals) of rendezvous and treasure hunt. Our goal is to find the smallest size of advice which enables the agents to solve these tasks at some cost @math in a network with @math edges. This size turns out to depend on the initial distance @math and on the ratio @math , which is the @math due to advice. For arbitrary graphs, we give upper and lower bounds of @math and @math , respectively, on the optimal size of advice. For the class of trees, we give nearly tight upper and lower bounds of @math and @math , respectively.
  @cite_30: We consider the problem of searching on m current rays for a target of unknown location. If no upper bound on the distance to the target is known in advance, then the optimal competitive ratio is 1+2mm (m−1)m−1. We show that even if an upper bound of D on the distance to the target is known in advance, then the competitive ratio of any search strategy is at least 1+2mm (m−1)m−1−O(1 log2D). This is again optimal – but in a stricter sense. In particular, this result implies the same lower bound for a robot searching for a target on infinite rays and finding it at a distance of D. To show that our lower bound is, indeed, optimal we construct a search strategy that achieves this ratio. Our strategy does not need to know an upper bound on the distance to the target in advance; it achieves a competitive ratio of 1+2mm (m−1)m−1−O(1 log2D) if the target is found at distance D. Finally, we also present a linear time algorithm to compute the strategy that allows the robot to search the farthest for a given competitive ratio C.
  @cite_36: We revisit the problem of searching for a target at an unknown location on a line when given upper and lower bounds on the distance D that separates the initial position of the searcher from the target. Prior to this work, only asymptotic bounds were known for the optimal competitive ratio achievable by any search strategy in the worst case. We present the first tight bounds on the exact optimal competitive ratio achievable, parametrized in terms of the given range for D, along with an optimal search strategy that achieves this competitive ratio. We prove that this optimal strategy is unique and that it cannot be computed exactly in general. We characterize the conditions under which an optimal strategy can be computed exactly and, when it cannot, we explain how numerical methods can be used efficiently. In addition, we answer several related open questions and we discuss how to generalize these results to m rays, for any m ≥ 2.
  @cite_48: We obtain several improved solutions for the deterministic rendezvous problem in general undirected graphs. Our solutions answer several problems left open in a recent paper by We also introduce an interesting variant of the rendezvous problem which we call the deterministic treasure hunt problem. Both the rendezvous and the treasure hunt problems motivate the study of universal traversal sequences and universal exploration sequences with some strengthened properties. We call such sequences strongly universal traversal (exploration) sequences. We give an explicit construction of strongly universal exploration sequences. The existence of strongly universal traversal sequences, as well as the solution of the most difficult variant of the deterministic treasure hunt problem, are left as intriguing open problems.
  @cite_50: In this paper we initiate a new area of study dealing with the best way to search a possibly unbounded region for an object. The model for our search algorithms is that we must pay costs proportional to the distance of the next probe position relative to our current position. This model is meant to give a realistic cost measure for a robot moving in the plane. We also examine the effect of decreasing the amount of a priori information given to search problems. Problems of this type are very simple analogues of non-trivial problems on searching an unbounded region, processing digitized images, and robot navigation. We show that for some simple search problems, knowing the general direction of the goal is much more informative than knowing the distance to the goal.
  @cite_31: In this paper, we investigate the explicit deterministic treasure hunt problem in a @math -vertex network. This problem was firstly introduced by Ta-Shma and Zwick in TZ07 [SODA'07]. Note also it is a variant of the well known rendezvous problem in which one of the robot (the treasure) is always stationary. In this paper, we propose an @math -time algorithm for the treasure hunt problem, which significantly improves the currently best known result of running time @math in TZ07 , where @math is a constant induced from the construction of an universal exploration sequence in R05,TZ07 , and @math is an arbitrary large, but fixed, integer constant. The treasure hunt problem also motivates the study of strongly universal exploration sequences. In this paper, we also propose a much better explicit construction for strongly universal exploration sequences compared to the one in TZ07 .
  @cite_12: 
summary: Treasure hunt, network exploration and rendezvous in networks are interrelated problems that have received much attention in recent literature. Treasure hunt has been investigated in the line @cite_36 @cite_12 , in the plane @cite_50 and in other terrains @cite_30 . Treasure hunt in anonymous networks (without any information about the network) has been studied in @cite_48 @cite_31 with the goal of minimizing cost.