×

Contract scheduling with predictions. (English) Zbl 07753305

Summary: Contract scheduling is a general technique that allows the design of systems with interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous work on this topic has assumed that the interruption is a worst-case deadline that is unknown to the scheduler. In this work, we study new settings in which the scheduler has access to some imperfect prediction in regards to the interruption. In the first setting, which is inspired by recent advances in learning-enhanced algorithms, the prediction describes the time that the interruption occurs. The second setting introduces a new model in which predictions are elicited as responses to a number of binary queries. For both settings, we investigate trade-offs between the robustness (i.e., the worst-case performance of the schedule if the prediction is generated adversarially) and the consistency (i.e., the performance assuming that the prediction is error-free). We also establish results on the performance of the schedules as a function of the prediction error.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

References:

[1] Angelopoulos, S. (2015). Further connections between contract-scheduling and ray-searching problems. InProceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1516-1522.
[2] Angelopoulos, S. (2021). Online search with a hint. InProceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS), pp. 51:1-51:16.
[3] Angelopoulos, S., D¨urr, C., Jin, S., Kamali, S., & Renault, M. P. (2020). Online computation with untrusted advice. InProceedings of the 11th International Conference on Innovations in Theoretical Computer Science (ITCS), pp. 52:1-52:15. · Zbl 07650400
[4] Angelopoulos, S., & Jin, S. (2019). Earliest-completion scheduling of contract algorithms with end guarantees. InProceedings of the 28th International Joint Conference on Artificial Intelligence, (IJCAI), pp. 5493-5499.
[5] Angelopoulos, S., & Kamali, S. (2021). Contract scheduling with predictions. InProceedings of the 35th AAAI Conference on Artificial Intelligence, AAAI 2021, pp. 11726-11733. AAAI Press.
[6] Angelopoulos, S., Kamali, S., & Zhang, D. (2022). Online search with best-price and querybased predictions. InProceedings of the 36th AAAI Conference on Artificial Intelligence, pp. 9652-9660. AAAI Press.
[7] Angelopoulos, S., & L´opez-Ortiz, A. (2009). Interruptible algorithms for multi-problem solving. InProceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), pp. 380-386.
[8] Angelopoulos, S., L´opez-Ortiz, A., & Hamel, A. (2008). Optimal scheduling of contract algorithms with soft deadlines. InProceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), pp. 868-873.
[9] Antoniadis, A., Coester, C., Elias, M., Polak, A., & Simon, B. (2020). Online metric algorithms with untrusted predictions. InProceedings of the 37th International Conference on Machine Learning (ICML), pp. 11453-11463.
[10] Bernstein, D. S., Finkelstein, L., & Zilberstein, S. (2003). Contract algorithms and robots on rays: Unifying two scheduling problems. InProceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1211-1217.
[11] Bernstein, D. S., Perkins, T. J., Zilberstein, S., & Finkelstein, L. (2002). Scheduling contract algorithms on multiple processors. InProceedings of the 18th AAAI Conference on Artificial Intelligence (AAAI), pp. 702-706.
[12] Boddy, M., & Dean, T. L. (1994). Deliberation scheduling for problem solving in timeconstrained environments.Artif. Intell.,67(2), 245-285. · Zbl 0809.68103
[13] Chrobak, M., & Kenyon-Mathieu, C. (2006). SIGACT news online algorithms column 10: Competitiveness via doubling.SIGACT News,37(4), 115-126.
[14] Cicalese, F. (2013).Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information. Monographs in Theoretical Computer Science. An EATCS Series. Springer. · Zbl 1295.68006
[15] Eberle, F., Lindermayr, A., Megow, N., N¨olke, L., & Schl¨oter, J. (2022). Robustification of online graph exploration methods. InProceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022, pp. 9732-9740. AAAI Press.
[16] Gollapudi, S., & Panigrahi, D. (2019). Online algorithms for rent-or-buy with expert advice. InProceedings of the 36th International Conference on Machine Learning (ICML), pp. 2319-2327.
[17] Horvitz, E. (1988).Reasoning about beliefs and actions under computational resource constraints.Int. J. Approx. Reasoning,2(3), 337-338.
[18] Im, S., Kumar, R., Qaem, M. M., & Purohit, M. (2021). Online knapsack with frequency predictions. InProceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 2733-2743.
[19] Kupavskii, A., & Welzl, E. (2019). Lower bounds for searching robots, some faulty.Distributed Computing,34(4), 229-237. · Zbl 1522.68069
[20] Lattanzi, S., Lavastida, T., Moseley, B., & Vassilvitskii, S. (2020). Online scheduling via learned weights. InProceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1859-1877. · Zbl 07304137
[21] Lee, R., Maghakian, J., Hajiesmaili, M. H., Li, J., Sitaraman, R. K., & Liu, Z. (2021). Online peak-aware energy scheduling with untrusted advice. Ine-Energy ’21: The Twelfth ACM International Conference on Future Energy Systems, pp. 107-123. ACM.
[22] Li, T., Yang, R., Qu, G., Shi, G., Yu, C., Wierman, A., & Low, S. H. (2022). Robustness and consistency in linear quadratic control with untrusted predictions.Proc. ACM Meas. Anal. Comput. Syst.,6(1), 18:1-18:35.
[23] L´opez-Ortiz, A., Angelopoulos, S., & Hamel, A. (2014). Optimal scheduling of contract algorithms for anytime problem-solving.J. Artif. Intell. Res.,51, 533-554. · Zbl 1367.68021
[24] Lykouris, T., & Vassilvitskii, S. (2018). Competitive caching with machine learned advice. InProceedings of the 35th International Conference on Machine Learning (ICML), pp. 3302-3311. · Zbl 1499.68415
[25] Mazumdar, A., & Saha, B. (2017). Clustering with noisy queries. InAnnual Conference on Neural Information Processing Systems (NIPS), Vol. 30, pp. 5788-5799.
[26] Mitzenmacher, M. (2020).Scheduling with predictions and the price of misprediction. InProceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS), Vol. 151, pp. 14:1-14:18. · Zbl 07650362
[27] Mitzenmacher, M., & Vassilvitskii, S. (2020). Algorithms with predictions. InBeyond the Worst-Case Analysis of Algorithms, pp. 646-662. Cambridge University Press. · Zbl 1540.68346
[28] Pelc, A. (2002). Searching games with errors - fifty years of coping with liars.Theor. Comput. Sci.,270(1-2), 71-109. · Zbl 0984.68041
[29] Purohit, M., Svitkina, Z., & Kumar, R. (2018). Improving online algorithms via ML predictions. InProceedings of the 31st Annual Conference on Neural Information Processing Systems (NIPS), pp. 9661-9670.
[30] Rivest, R. L., Meyer, A. R., Kleitman, D. J., Winklmann, K., & Spencer, J. (1980). Coping with errors in binary search procedures.J. Comput. Syst. Sci.,20(3), 396-404. · Zbl 0443.68043
[31] Russell, S. J., & Zilberstein, S. (1991). Composing real-time systems. InProceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI), pp. 212-217. · Zbl 0746.68085
[32] Sun, B., Lee, R., Hajiesmaili, M., Wierman, A., & Tsang, D. (2021).Pareto-optimal learning-augmented algorithms for online conversion problems. InProceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 10339-10350.
[33] Wei, A., & Zhang, F. (2020).Optimal robustness-consistency trade-offs for learningaugmented online algorithms. InProceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS).
[34] Xu, C., & Moseley, B. (2022). Learning-augmented algorithms for online Steiner trees. In AAAI, pp. 8744-8752. AAAI Press.
[35] Zilberstein, S. (1996). Using anytime algorithms in intelligent systems.AI Magazine,17(3), 73-83.
[36] Zilberstein, S., & Russell, S. J. (1993). Anytime sensing, planning and action: A practical model for robot control. InProceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1402-1407.
[37] Zilberstein, S., Charpillet, F., & Chassaing, P. (2003). Optimal sequencing of contract algorithms..Ann. Math. Artif. Intell.,39(1-2), 1-18. · Zbl 1045.68129
[38] Zilberstein, S., & Russell, S. J. (1996). Optimal composition of real-time systems.Artif. Intell.,82(1-2), 181-213 · Zbl 1506.68012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.