Technical Report No. 112 - Abstract

Sven Schuierer
Searching on m Bounded Rays Optimally

We consider the problem of searching on m current rays for a target of unknown location. It is well-known that the optimal strategy to solve this problem achieves a competitive ratio of C_m = 1 + 2m^m / (m-1)^m-1. We investigate the case where the target is known to be within a fixed distance D of the origin. We present an algorithm to compute the optimal competitive ratio C^D_m that can be achieved by a deterministic on-line strategy.