The Ultimate Strategy to Search on m-Rays? A. López-Ortiz
and S. Schuierer. To appear, Theoretical Computer Science. Extended
abstract also in Proceedings of Fourth Computing and Combinatorics
Conference, 1998. PostScript file.
Abstract.
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^2 D) 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^2 D) if the target is found at distance D
Finally, we also present an algorithm to compute the strategy that
allows the robot to search the farthest for a given competitive ratio
C.