Contract Algorithms and Robots on Rays: Unifying Two Scheduling Problems
Daniel S. Bernstein
Lev Finkelstein
Shlomo Zilberstein
Abstract
We study two apparently different, but formally similar, scheduling
problems. The first problem involves contract algorithms, which can
trade off run time for solution quality, as long as the amount of
available run time is known in advance. The problem is to schedule
contract algorithms to run on parallel processors, under the condition
that an interruption can occur at any time, and upon interruption a
solution to any one of a number of problems can be requested. Schedules
are compared in terms of acceleration ratio, which is a worst-case
measure of efficiency. We provide a schedule and prove its optimality
among a particular class of schedules. Our second problem involves
multiple robots searching for a goal on one of multiple rays. Search
strategies are compared in terms of time-competitive ratio, the ratio of
the total search time to the time it would take for one robot to
traverse directly to the goal. We demonstrate that search strategies
and contract schedules are formally equivalent. In addition, for our
class of schedules, we derive a formula relating the acceleration ratio
of a schedule to the time-competitive ratio of the corresponding search
strategy.
Download
[pdf]