Optimal schedules for monitoring anytime algorithms

✍ Scribed by Lev Finkelstein; Shaul Markovitch

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 378 KB
• Volume: 126
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/s0004-3702(00)00072-2

✦ Synopsis

Monitoring anytime algorithms can significantly improve their performance. This work deals with the problem of off-line construction of monitoring schedules. We study a model where queries are submitted to the monitored process in order to detect satisfaction of a given goal predicate. The queries consume time from the monitored process, thus delaying the time of satisfying the goal condition. We present a formal model for this class of problems and provide a theoretical analysis of the class of optimal schedules. We then introduce an algorithm for constructing optimal monitoring schedules and prove its correctness. We continue with distribution-based analysis for common distributions, accompanied by experimental results. We also provide a theoretical comparison of our methodology with existing monitoring techniques.