Interruptible Algorithms for Multi-Problem Solving

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. Spyros Angelopoulos, Alejandro Lopez-Ortiz