Interruptible algorithms for Multi-Problem Solving
[.pdf]
Abstract
In this paper we address the problem of designing an interruptible system
in a setting in which n problem instances, all equally important,
must be solved. The system involves scheduling executions of contract algorithms
(which offer a trade-off between allowable computation time and quality of the solution)
in m identical parallel processors. When an interruption occurs, the system must
report a solution to each of the n problem instances.
The quality of this output is then compared to the best-possible algorithm that
has foreknowledge of the interruption time and must, likewise,
produce solutions to all n problem instances.
This extends the well-studied setting in which only one problem instance
is queried at interruption time.
We propose a schedule which we prove is optimal for the case of a single processor.
For multiple processors, we show that the quality of the schedule is within a small factor from optimal.
Bibtex Entry
