### Technical Report No. 100, May 1998 - Abstract

** A. L\'opez-Ortiz, S. Schuierer**

* The Ultimate Strategy to Search on m Rays?*

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 + 2
*m*^{m} / (*m* -
1)^{m-1}. We show that 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 + 2
*m*^{m} / (*m* - 1)^{m-1}
- O(1 / log D^{2}) which is again optimal--but in a
stricter sense.

To show the optimality of our lower bound we construct a search
strategy that achieves this ratio. Surprisingly, 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 + 2 *m*^{m} /
(*m* - 1)^{m-1} - O(1 / log D^{2}) if the
target is found at distance *D*.

Report No. 100(PostScript)