Contract Scheduling with Distributional and Multiple Advice
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910415059943424 |
|---|---|
| author | Angelopoulos, Spyros Bienkowski, Marcin Dürr, Christoph Simon, Bertrand |
| author_facet | Angelopoulos, Spyros Bienkowski, Marcin Dürr, Christoph Simon, Bertrand |
| contents | Contract scheduling is a widely studied framework for designing real-time systems with interruptible capabilities. Previous work has showed that a prediction on the interruption time can help improve the performance of contract-based systems, however it has relied on a single prediction that is provided by a deterministic oracle. In this work, we introduce and study more general and realistic learning-augmented settings in which the prediction is in the form of a probability distribution, or it is given as a set of multiple possible interruption times. For both prediction settings, we design and analyze schedules which perform optimally if the prediction is accurate, while simultaneously guaranteeing the best worst-case performance if the prediction is adversarial. We also provide evidence that the resulting system is robust to prediction errors in the distributional setting. Last, we present an experimental evaluation that confirms the theoretical findings, and illustrates the performance improvements that can be attained in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_12485 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Contract Scheduling with Distributional and Multiple Advice Angelopoulos, Spyros Bienkowski, Marcin Dürr, Christoph Simon, Bertrand Data Structures and Algorithms Artificial Intelligence Machine Learning Contract scheduling is a widely studied framework for designing real-time systems with interruptible capabilities. Previous work has showed that a prediction on the interruption time can help improve the performance of contract-based systems, however it has relied on a single prediction that is provided by a deterministic oracle. In this work, we introduce and study more general and realistic learning-augmented settings in which the prediction is in the form of a probability distribution, or it is given as a set of multiple possible interruption times. For both prediction settings, we design and analyze schedules which perform optimally if the prediction is accurate, while simultaneously guaranteeing the best worst-case performance if the prediction is adversarial. We also provide evidence that the resulting system is robust to prediction errors in the distributional setting. Last, we present an experimental evaluation that confirms the theoretical findings, and illustrates the performance improvements that can be attained in practice. |
| title | Contract Scheduling with Distributional and Multiple Advice |
| topic | Data Structures and Algorithms Artificial Intelligence Machine Learning |
| url | https://arxiv.org/abs/2404.12485 |