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)