Technical Report No. 111 - Abstract

Sven Schuierer
Lower Bounds For Randomized Searching on m Rays

We consider the problem of on-line searching on m rays. A point robot is assumed to stand at the origin of m concurrent rays one of which contains a goal g that the point robot has to reach. Neither the ray containing g nor the distance to g are known to the robot. The only way the robot can detect g is by reaching its location. We use the competitive ratio to measure the performance of a strategy. We present a simple proof of a tight lower bound for randomized strategies to search on m rays. In particular, we show in our proof that there is an optimal randomized strategy that visits the rays in cyclic order. We also obtain a bound on the convergence rate to the optimal competitive ratio for a fixed m if the goal has a distance of at most D to the origin. Finally, we show that the optimal competitive ratio is asymptotically given by 1 + 2*1.544m as m goes to infinity.