Institut für Informatik

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 Cm = 1 + 2mm / (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 CDm that can be achieved by a deterministic on-line strategy.

Report No. 112 (PostScript)