Interruptible algorithms for multiproblem solving

Spyros Angelopoulos () and Alejandro López-Ortiz
Additional contact information
Spyros Angelopoulos: Sorbonne Université
Alejandro López-Ortiz: University of Waterloo

Journal of Scheduling, 2020, vol. 23, issue 4, No 3, 464 pages

Abstract: Abstract In this paper, we address the problem of designing an interruptible system in a setting which involves n problem instances. The system schedules executions of a contract algorithm (which offers a trade-off between allowable computation time and quality of the solution) in m identical parallel processors. When an interruption occurs, the system outputs the currently best 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. In this work, we first introduce new measures for evaluating the performance of interruptible systems in this setting. In particular, we propose the deficiency of a schedule as a performance measure that meets the requirements of the problem at hand. We then present a schedule whose performance we prove that is within a small factor from optimal in the general, multiprocessor setting. We also show several lower bounds on the deficiency of schedules on a single processor. More precisely, we prove a general lower bound of $$(n+1)/n$$ ( n + 1 ) / n , an improved lower bound for the two-problem setting ( $$n=2$$ n = 2 ), and a tight lower bound for the class of round-robin schedules. Our techniques can also yield a simpler, alternative proof of the main result of Bernstein et al. (in: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), pp 1211–1217, 2003) concerning the performance of cyclic schedules in multiprocessor environments.

Keywords: Anytime computation; Contract algorithms; Interruptible algorithms; Acceleration ratio; Scheduling problems in artificial intelligence; Performance measures in scheduling (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-020-00644-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:23:y:2020:i:4:d:10.1007_s10951-020-00644-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-020-00644-9

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().