Scheduling Contract Algorithms on Multiple Processors  Daniel S.
Bernstein, Theodore J. Perkins, and Shlomo Zilberstein,
University of Massachusetts; Lev Finkelstein, Technion - Israel
Institute of Technology  Anytime algorithms offer a tradeoff
between computation time and the quality of the result returned.
They can be divided into two classes: contract algorithms, for
which the total run time must be specified in advance, and
interruptible algorithms, which can be queried at any time for a
solution. An interruptible algorithm can be constructed from a
contract algorithm by repeatedly activating the contract
algorithm with increasing run times. The acceleration ratio of a
run-time schedule is a worst-case measure of how inefficient the
constructed interruptible algorithm is compared to the contract
algorithm. The smallest acceleration ratio achievable on a
single processor is known. Using multiple processors, smaller
acceleration ratios are possible. In this paper, we provide a
schedule for m processors and