Search and Rescue on the Ring

This paper studies the online problem of search and rescue on a (unit) ring. Assuming that an object is located somewhere unknown on the ring, we aim to find the object and deliver it to a designated destination by one or more mobile agents, so that the total time spent is minimized. The agent(s) can only move along the ring, and is initially located a distance of [Formula: see text] away from the destination. For single-agent search and rescue, we present an optimal deterministic algorithm with a competitive ratio of [Formula: see text], and as well as randomized algorithms corresponding to [Formula: see text] and [Formula: see text], whose expected competitive ratios can be accurately computed by non-linear programming. For the two-agent search and rescue, we propose deterministic algorithms with competition ratios depending on whether the agents can communicate through the radios.