---
title: "Interruptible Algorithms for Multi-Problem Solving"
authors:
  - "Spyros Angelopoulos"
  - "Alejandro López-Ortiz"
doi: ""
url: "https://ijcai.org/proceedings/2009/71"
pdf: "https://ijcai.org/proceedings/2009/0071.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "380-385"
track: ""
keywords:
---

# Interruptible Algorithms for Multi-Problem Solving

Spyros Angelopoulos, Alejandro López-Ortiz

*Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence*, pages 380-385.

## 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