Optimal Schedules for Parallelizing Anytime Algorithms: the Case of Independent Processes

Lev Finkelstein, Shaul Markovitch, and Ehud Rivlin.
Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Independent Processes.
In AAAI/IAAI, 719-724, 2002

Online Version

A pdf version is available for download.

Abstract

The performance of anytime algorithms having a nondeterministic nature can be improved by solving simultaneously several instances of the algorithm-problem pairs. These pairs may include different instances of a problem (like starting from a different initial state), different algorithms (if several alternatives exist), or several instances of the same algorithm (for nondeterministic algorithms). In this paper we present a general framework for optimal parallelization of independent processes. We show a mathematical model for this framework, present algorithms for optimal scheduling, and demonstrate its usefulness on a real problem.

Co-authors

Bibtex Entry

@inproceedings{FinkelsteinMR02i,
  title = {Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Independent Processes.},
  author = {Lev Finkelstein and Shaul Markovitch and Ehud Rivlin},
  year = {2002},
  booktitle = {AAAI/IAAI},
  pages = {719-724},
  abstract = {The performance of anytime algorithms having a nondeterministic nature can be improved by solving simultaneously several instances of the algorithm-problem pairs. These pairs may include different instances of a problem (like starting from a different initial state), different algorithms (if several alternatives exist), or several instances of the same algorithm (for nondeterministic algorithms). In this paper we present a general framework for optimal parallelization of independent processes. We show a mathematical model for this framework, present algorithms for optimal scheduling, and demonstrate its usefulness on a real problem.}
}