Online interval scheduling with predictions. (English) Zbl 07789705
Morin, Pat (ed.) et al., Algorithms and data structures. 18th international symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14079, 193-207 (2023).
Summary: In online interval scheduling, the input is an online sequence of intervals, and the goal is to accept a maximum number of non-overlapping intervals. In the more general disjoint path allocation problem, the input is a sequence of requests, each involving a pair of vertices of a known graph, and the goal is to accept a maximum number of requests forming edge-disjoint paths between accepted pairs. These problems have been studied under extreme settings without information about the input or with error-free advice. We study an intermediate setting with a potentially erroneous prediction that specifies the set of intervals/requests forming the input sequence. For both problems, we provide tight upper and lower bounds on the competitive ratios of online algorithms as a function of the prediction error. For disjoint path allocation, our results rule out the possibility of obtaining a better competitive ratio than that of a simple algorithm that fully trusts predictions, whereas, for interval scheduling, we develop a superior algorithm. We also present asymptotically tight trade-offs between consistency (competitive ratio with error-free predictions) and robustness (competitive ratio with adversarial predictions) of interval scheduling algorithms. Finally, we provide experimental results on real-world scheduling workloads that confirm our theoretical analysis.
For the entire collection see [Zbl 1528.68033].
For the entire collection see [Zbl 1528.68033].
Keywords:
online interval scheduling; algorithms with prediction; competitive analysis; disjoint pathsSoftware:
GitHubReferences:
| [1] | Algorithms with predictions. https://algorithms-with-predictions.github.io/. Accessed 19 Feb 2023 |
| [2] | Interval scheduling with prediction. https://github.com/shahink84/IntervalSchedulingWithPrediction. Accessed 19 Feb 2023 |
| [3] | Angelopoulos, S., Dürr, C., Jin, S., Kamali, S., Renault, M.: Online computation with untrusted advice. In: Proceedings of the ITCS. LIPIcs, vol. 151, pp. 52:1-52:15 (2020) · Zbl 07650400 |
| [4] | Angelopoulos, S., Kamali, S., Shadkami, K.: Online bin packing with predictions. In: Proceedings of the IJCAI, pp. 4574-4580 (2022) |
| [5] | Angelopoulos, S., Kamali, S., Zhang, D.: Online search with best-price and query-based predictions. In: Proceedings of the AAAI, pp. 9652-9660 (2023) |
| [6] | Angelopoulos, S., Kamali, S.: Contract scheduling with predictions. In: Proceedings of the AAAI, pp. 11726-11733. AAAI Press (2021) |
| [7] | Angelopoulos, S., Arsénio, D., Kamali, S.: Competitive sequencing with noisy advice. CoRR abs/2111.05281 (2021) |
| [8] | Antoniadis, A., et al.: Paging with succinct predictions. In: Proceedings of the ICML (2023, to appear) |
| [9] | Antoniadis, A., Gouleakis, T., Kleer, P., Kolev, P.: Secretary and online matching problems with machine learned advice. In: Proceedings of the NeurIPS (2020) · Zbl 07705149 |
| [10] | Awerbuch, B., Bartal, Y., Fiat, A., Rosén, A.: Competitive non-preemptive call control. In: Proceedings of the SODA, pp. 312-320 (1994) · Zbl 0876.68047 |
| [11] | Azar, Y., Leonardi, S., Touitou, N.: Flow time scheduling with uncertain processing time. In: Proceedings of the STOC, pp. 1070-1080 (2021) · Zbl 07765232 |
| [12] | Azar, Y., Panigrahi, D., Touitou, N.: Online graph algorithms with predictions. In: Proceedings of the SODA, pp. 35-66 (2022) · Zbl 07883584 |
| [13] | Balkanski, E., Gkatzelis, V., Tan, X.: Strategyproof scheduling with predictions. In: Proceedings of the ITCS. LIPIcs, vol. 251, pp. 11:1-11:22 (2023) |
| [14] | Bampis, E., Dogeas, K., Kononov, A.V., Lucarelli, G., Pascual, F.: Scheduling with untrusted predictions. In: Proceedings of the IJCAI, pp. 4581-4587 (2022) |
| [15] | Banerjee, S., Cohen-Addad, V., A., Li, Z.: Graph searching with predictions. In: Proceedings of the ITCS. LIPIcs, vol. 251, pp. 12:1-12:24 (2023) |
| [16] | Barhum, K.; Böckenhauer, H-J; Forišek, M.; Gebauer, H.; Hromkovič, J.; Krug, S.; Smula, J.; Steffen, B.; Geffert, V.; Preneel, B.; Rovan, B.; Štuller, J.; Tjoa, AM, On the power of advice and randomization for the disjoint path allocation problem, SOFSEM 2014: Theory and Practice of Computer Science, 89-101 (2014), Cham: Springer, Cham · Zbl 1432.68009 · doi:10.1007/978-3-319-04298-5_9 |
| [17] | Berg, M., Boyar, J., Favrholdt, L.M., Larsen, K.S.: Online interval scheduling with predictions. ArXiv (2023). arXiv:2302.13701. To appear in 18th WADS, 2023 |
| [18] | Böckenhauer, H.; Benz, NC; Komm, D., Call admission problems on trees, Theor. Comput. Sci., 922, 410-423 (2022) · Zbl 1535.68488 · doi:10.1016/j.tcs.2022.04.042 |
| [19] | Böckenhauer, H.; Komm, D.; Wegner, R., Call admission problems on grids with advice, Theor. Comput. Sci., 918, 77-93 (2022) · Zbl 1520.68113 · doi:10.1016/j.tcs.2022.03.022 |
| [20] | Borodin, A.; El-Yaniv, R., Online Computation and Competitive Analysis (1998), Cambridge: Cambridge University Press, Cambridge · Zbl 0931.68015 |
| [21] | Boyar, J., Favrholdt, L.M., Larsen, K.S.: Online unit profit knapsack with untrusted predictions. In: Proceedings of the SWAT. LIPIcs, vol. 227, pp. 20:1-20:17 (2022) · Zbl 07853692 |
| [22] | Boyar, J.; Favrholdt, LM; Kudahl, C.; Mikkelsen, JW, The advice complexity of a class of hard online problems, Theory Comput. Syst., 61, 4, 1128-1177 (2017) · Zbl 1387.68302 · doi:10.1007/s00224-016-9688-y |
| [23] | Chapin, SJ; Feitelson, DG; Rudolph, L., Benchmarks and standards for the evaluation of parallel job schedulers, Job Scheduling Strategies for Parallel Processing, 67-90 (1999), Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-47954-6_4 |
| [24] | Chen, J.Y., et al.: Triangle and four cycle counting with predictions in graph streams. In: Proceedings of the ICLR (2022) |
| [25] | Chen, J.Y., Silwal, S., Vakilian, A., Zhang, F.: Faster fundamental graph algorithms via learned predictions. In: Proceedings of the ICML. PLMR, vol. 162, pp. 3583-3602 (2022) |
| [26] | Wagner, D.; Weihe, K., A linear-time algorithm for edge-disjoint paths in planar graphs, Combinatorica, 15, 135-150 (1995) · Zbl 0841.05086 · doi:10.1007/BF01294465 |
| [27] | Eberle, F., Lindermayr, A., Megow, N., Nölke, L., Schlöter, J.: Robustification of online graph exploration methods. In: Proceedings of the AAAI, pp. 9732-9740 (2022) |
| [28] | Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multicommodity flow problems, SIAM J. Comput., 5, 4, 691-703 (1976) · Zbl 0358.90021 · doi:10.1137/0205048 |
| [29] | Frank, A., Edge-disjoint paths in planar graphs, J. Combin. Theory Ser. B, 39, 164-178 (1985) · Zbl 0583.05036 · doi:10.1016/0095-8956(85)90046-2 |
| [30] | Garg, N.; Vazirani, VV; Yannakakis, M., Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18, 3-20 (1977) · Zbl 0873.68075 · doi:10.1007/BF02523685 |
| [31] | Gebauer, H.; Komm, D.; Královič, R.; Královič, R.; Smula, J.; Xu, D.; Du, D.; Du, D., Disjoint path allocation with sublinear advice, Computing and Combinatorics, 417-429 (2015), Cham: Springer, Cham · Zbl 1465.68103 · doi:10.1007/978-3-319-21398-9_33 |
| [32] | Im, S., Kumar, R., Qaem, M.M., Purohit, M.: Non-clairvoyant scheduling with predictions. In: Proceedings of the SPAA, pp. 285-294 (2021) |
| [33] | Im, S., Kumar, R., Qaem, M.M., Purohit, M.: Online knapsack with frequency predictions. In: Proceedings of the NeurIPS, pp. 2733-2743 (2021) |
| [34] | Matsumoto, K.; Nishizeki, T.; Saito, N., An efficient algorithm for finding multi-commodity flows in planar networks, SIAM J. Comput., 14, 2, 289-302 (1985) · Zbl 0572.90027 · doi:10.1137/0214023 |
| [35] | Kolen, AW; Lenstra, JK; Papadimitriou, CH; Spieksma, FC, Interval scheduling: a survey, Nav. Res. Logist., 54, 5, 530-543 (2007) · Zbl 1143.90337 · doi:10.1002/nav.20231 |
| [36] | Lattanzi, S., Lavastida, T., Moseley, B., Vassilvitskii, S.: Online scheduling via learned weights. In: Proceedings of the SODA, pp. 1859-1877 (2020) · Zbl 07304137 |
| [37] | Lavastida, T., Moseley, B., Ravi, R., Xu, C.: Learnable and instance-robust predictions for online matching, flows and load balancing. In: Proceedings of the ESA. LIPIcs, vol. 204, pp. 59:1-59:17 (2021) · Zbl 07740914 |
| [38] | Lavastida, T., Moseley, B., Ravi, R., Xu, C.: Using predicted weights for ad delivery. In: Proceedings of the ACDA, pp. 21-31 (2021) |
| [39] | Lee, R., Maghakian, J., Hajiesmaili, M., Li, J., Sitaraman, R.K., Liu, Z.: Online peak-aware energy scheduling with untrusted advice. In: Proceedings of the e-Energy, pp. 107-123 (2021) |
| [40] | Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. In: Proceedings of the ICML. PMLR, vol. 80, pp. 3302-3311 (2018) · Zbl 1499.68415 |
| [41] | Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithms, pp. 646-662. Cambridge University Press (2020) · Zbl 1540.68346 |
| [42] | Nishizeki, T.; Vygen, J.; Zhou, X., The edge-disjoint paths problem is NP-complete for series-parallel graphs, Discret. Appl. Math., 115, 1-3, 177-186 (2001) · Zbl 1001.68091 · doi:10.1016/S0166-218X(01)00223-2 |
| [43] | Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In: Proceedings of the NeurIPS, pp. 9661-9670 (2018) |
| [44] | Rohatgi, D.: Near-optimal bounds for online caching with machine learned advice. In: Proceedings of the SODA, pp. 1834-1845 (2020) · Zbl 07304135 |
| [45] | Wei, A., Zhang, F.: Optimal robustness-consistency trade-offs for learning-augmented online algorithms. In: Proceedings of the NeurIPS (2020) |
| [46] | Wei, A.: Better and simpler learning-augmented online caching. In: Proceedings of the APPROX/RANDOM. LIPIcs, vol. 176, pp. 60:1-60:17 (2020) · Zbl 07758362 |
| [47] | Zeynali, A., Sun, B., Hajiesmaili, M., Wierman, A.: Data-driven competitive algorithms for online knapsack and set cover. In: Proceedings of the AAAI, pp. 10833-10841 (2021) |
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.
