Uni-Logo

Department of Computer Science
 

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 mm / (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 mm / (m - 1)m-1 - O(1 / log D2) 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 mm / (m - 1)m-1 - O(1 / log D2) if the target is found at distance D.


Report No. 100(PostScript)