Further Connections Between Contract-Scheduling and Ray-Searching\n Problems

Abstract

This paper addresses two classes of different, yet interrelated optimization\nproblems. The first class of problems involves a robot that must locate a\nhidden target in an environment that consists of a set of concurrent rays. The\nsecond class pertains to the design of interruptible algorithms by means of a\nschedule of contract algorithms. We study several variants of these families of\nproblems, such as searching and scheduling with probabilistic considerations,\nredundancy and fault-tolerance issues, randomized strategies, and trade-offs\nbetween performance and preemptions. For many of these problems we present the\nfirst known results that apply to multi-ray and multi-problem domains. Our\nobjective is to demonstrate that several well-motivated settings can be\naddressed using the same underlying approach.\n