Further Connections Between Contract-Scheduling and Ray-Searching
  Problems
  This paper addresses two classes of different, yet interrelated optimization
problems. The first class of problems involves a robot that must locate a
hidden target in an environment that consists of a set of concurrent rays. The
second class pertains to the design of interruptible algorithms by means of a
schedule of contract algorithms. We study several variants of these families of
problems, such as searching and scheduling with probabilistic considerations,
redundancy and fault-tolerance issues, randomized strategies, and trade-offs
between performance and preemptions. For many of these problems we present the
first known results that apply to multi-ray and multi-problem domains. Our
objective is to demonstrate that several well-motivated settings can be
addressed using the same underlying approach.
