Miscelaneous
We list some papers that, although tangential to the scope of this project, are pertinent to online computation.
1. Connections between contract-scheduling and ray-searching problems
(by Spyros Angelopoulos)
In this work we address 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.
This paper appeared to the proceedings of the 24th International Joint Conference on Artificial Intelligence, 2015 (IJCAI-15)