{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T23:25:19Z","timestamp":1773617119750,"version":"3.50.1"},"publisher-location":"Cham","reference-count":47,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031389054","type":"print"},{"value":"9783031389061","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-38906-1_14","type":"book-chapter","created":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:05:14Z","timestamp":1690473914000},"page":"193-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Online Interval Scheduling with\u00a0Predictions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0725-8341","authenticated-orcid":false,"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3054-2997","authenticated-orcid":false,"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1404-2212","authenticated-orcid":false,"given":"Shahin","family":"Kamali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0560-3794","authenticated-orcid":false,"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,28]]},"reference":[{"key":"14_CR1","unstructured":"Algorithms with predictions. https:\/\/algorithms-with-predictions.github.io\/. Accessed 19 Feb 2023"},{"key":"14_CR2","unstructured":"Interval scheduling with prediction. https:\/\/github.com\/shahink84\/IntervalSchedulingWithPrediction. Accessed 19 Feb 2023"},{"key":"14_CR3","unstructured":"Angelopoulos, S., D\u00fcrr, C., Jin, S., Kamali, S., Renault, M.: Online computation with untrusted advice. In: Proceedings of the ITCS. LIPIcs, vol. 151, pp. 52:1\u201352:15 (2020)"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., Kamali, S., Shadkami, K.: Online bin packing with predictions. In: Proceedings of the IJCAI, pp. 4574\u20134580 (2022)","DOI":"10.24963\/ijcai.2022\/635"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., Kamali, S., Zhang, D.: Online search with best-price and query-based predictions. In: Proceedings of the AAAI, pp. 9652\u20139660 (2023)","DOI":"10.1609\/aaai.v36i9.21199"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., Kamali, S.: Contract scheduling with predictions. In: Proceedings of the AAAI, pp. 11726\u201311733. AAAI Press (2021)","DOI":"10.1609\/aaai.v35i13.17394"},{"key":"14_CR7","unstructured":"Angelopoulos, S., Ars\u00e9nio, D., Kamali, S.: Competitive sequencing with noisy advice. CoRR abs\/2111.05281 (2021)"},{"key":"14_CR8","unstructured":"Antoniadis, A., et al.: Paging with succinct predictions. In: Proceedings of the ICML (2023, to appear)"},{"key":"14_CR9","unstructured":"Antoniadis, A., Gouleakis, T., Kleer, P., Kolev, P.: Secretary and online matching problems with machine learned advice. In: Proceedings of the NeurIPS (2020)"},{"key":"14_CR10","unstructured":"Awerbuch, B., Bartal, Y., Fiat, A., Ros\u00e9n, A.: Competitive non-preemptive call control. In: Proceedings of the SODA, pp. 312\u2013320 (1994)"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Azar, Y., Leonardi, S., Touitou, N.: Flow time scheduling with uncertain processing time. In: Proceedings of the STOC, pp. 1070\u20131080 (2021)","DOI":"10.1145\/3406325.3451023"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Azar, Y., Panigrahi, D., Touitou, N.: Online graph algorithms with predictions. In: Proceedings of the SODA, pp. 35\u201366 (2022)","DOI":"10.1137\/1.9781611977073.3"},{"key":"14_CR13","unstructured":"Balkanski, E., Gkatzelis, V., Tan, X.: Strategyproof scheduling with predictions. In: Proceedings of the ITCS. LIPIcs, vol. 251, pp. 11:1\u201311:22 (2023)"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Bampis, E., Dogeas, K., Kononov, A.V., Lucarelli, G., Pascual, F.: Scheduling with untrusted predictions. In: Proceedings of the IJCAI, pp. 4581\u20134587 (2022)","DOI":"10.24963\/ijcai.2022\/636"},{"key":"14_CR15","unstructured":"Banerjee, S., Cohen-Addad, V., A., Li, Z.: Graph searching with predictions. In: Proceedings of the ITCS. LIPIcs, vol. 251, pp. 12:1\u201312:24 (2023)"},{"key":"14_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-319-04298-5_9","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"K Barhum","year":"2014","unstructured":"Barhum, K., B\u00f6ckenhauer, H.-J., Fori\u0161ek, M., Gebauer, H., Hromkovi\u010d, J., Krug, S., Smula, J., Steffen, B.: On the power of advice and randomization for the disjoint path allocation problem. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 89\u2013101. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-04298-5_9"},{"key":"14_CR17","unstructured":"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"},{"key":"14_CR18","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1016\/j.tcs.2022.04.042","volume":"922","author":"H B\u00f6ckenhauer","year":"2022","unstructured":"B\u00f6ckenhauer, H., Benz, N.C., Komm, D.: Call admission problems on trees. Theor. Comput. Sci. 922, 410\u2013423 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR19","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.tcs.2022.03.022","volume":"918","author":"H B\u00f6ckenhauer","year":"2022","unstructured":"B\u00f6ckenhauer, H., Komm, D., Wegner, R.: Call admission problems on grids with advice. Theor. Comput. Sci. 918, 77\u201393 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR20","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"key":"14_CR21","unstructured":"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\u201320:17 (2022)"},{"issue":"4","key":"14_CR22","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1007\/s00224-016-9688-y","volume":"61","author":"J Boyar","year":"2017","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Mikkelsen, J.W.: The advice complexity of a class of hard online problems. Theory Comput. Syst. 61(4), 1128\u20131177 (2017)","journal-title":"Theory Comput. Syst."},{"key":"14_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-47954-6_4","volume-title":"Job Scheduling Strategies for Parallel Processing","author":"SJ Chapin","year":"1999","unstructured":"Chapin, S.J., et al.: Benchmarks and standards for the evaluation of parallel job schedulers. In: Feitelson, D.G., Rudolph, L. (eds.) JSSPP 1999. LNCS, vol. 1659, pp. 67\u201390. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-47954-6_4"},{"key":"14_CR24","unstructured":"Chen, J.Y., et al.: Triangle and four cycle counting with predictions in graph streams. In: Proceedings of the ICLR (2022)"},{"key":"14_CR25","unstructured":"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\u20133602 (2022)"},{"key":"14_CR26","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF01294465","volume":"15","author":"D Wagner","year":"1995","unstructured":"Wagner, D., Weihe, K.: A linear-time algorithm for edge-disjoint paths in planar graphs. Combinatorica 15, 135\u2013150 (1995)","journal-title":"Combinatorica"},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"Eberle, F., Lindermayr, A., Megow, N., N\u00f6lke, L., Schl\u00f6ter, J.: Robustification of online graph exploration methods. In: Proceedings of the AAAI, pp. 9732\u20139740 (2022)","DOI":"10.1609\/aaai.v36i9.21208"},{"issue":"4","key":"14_CR28","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691\u2013703 (1976)","journal-title":"SIAM J. Comput."},{"key":"14_CR29","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/0095-8956(85)90046-2","volume":"39","author":"A Frank","year":"1985","unstructured":"Frank, A.: Edge-disjoint paths in planar graphs. J. Combin. Theory Ser. B 39, 164\u2013178 (1985)","journal-title":"J. Combin. Theory Ser. B"},{"key":"14_CR30","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1977","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3\u201320 (1977)","journal-title":"Algorithmica"},{"key":"14_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/978-3-319-21398-9_33","volume-title":"Computing and Combinatorics","author":"H Gebauer","year":"2015","unstructured":"Gebauer, H., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., Smula, J.: Disjoint path allocation with sublinear advice. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 417\u2013429. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21398-9_33"},{"key":"14_CR32","doi-asserted-by":"crossref","unstructured":"Im, S., Kumar, R., Qaem, M.M., Purohit, M.: Non-clairvoyant scheduling with predictions. In: Proceedings of the SPAA, pp. 285\u2013294 (2021)","DOI":"10.1145\/3409964.3461790"},{"key":"14_CR33","unstructured":"Im, S., Kumar, R., Qaem, M.M., Purohit, M.: Online knapsack with frequency predictions. In: Proceedings of the NeurIPS, pp. 2733\u20132743 (2021)"},{"issue":"2","key":"14_CR34","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/0214023","volume":"14","author":"K Matsumoto","year":"1985","unstructured":"Matsumoto, K., Nishizeki, T., Saito, N.: An efficient algorithm for finding multi-commodity flows in planar networks. SIAM J. Comput. 14(2), 289\u2013302 (1985)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"14_CR35","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1002\/nav.20231","volume":"54","author":"AW Kolen","year":"2007","unstructured":"Kolen, A.W., Lenstra, J.K., Papadimitriou, C.H., Spieksma, F.C.: Interval scheduling: a survey. Nav. Res. Logist. 54(5), 530\u2013543 (2007)","journal-title":"Nav. Res. Logist."},{"key":"14_CR36","doi-asserted-by":"crossref","unstructured":"Lattanzi, S., Lavastida, T., Moseley, B., Vassilvitskii, S.: Online scheduling via learned weights. In: Proceedings of the SODA, pp. 1859\u20131877 (2020)","DOI":"10.1137\/1.9781611975994.114"},{"key":"14_CR37","unstructured":"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\u201359:17 (2021)"},{"key":"14_CR38","doi-asserted-by":"crossref","unstructured":"Lavastida, T., Moseley, B., Ravi, R., Xu, C.: Using predicted weights for ad delivery. In: Proceedings of the ACDA, pp. 21\u201331 (2021)","DOI":"10.1137\/1.9781611976830.3"},{"key":"14_CR39","doi-asserted-by":"crossref","unstructured":"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\u2013123 (2021)","DOI":"10.1145\/3447555.3464860"},{"key":"14_CR40","unstructured":"Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. In: Proceedings of the ICML. PMLR, vol. 80, pp. 3302\u20133311 (2018)"},{"key":"14_CR41","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithms, pp. 646\u2013662. Cambridge University Press (2020)","DOI":"10.1017\/9781108637435.037"},{"issue":"1\u20133","key":"14_CR42","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0166-218X(01)00223-2","volume":"115","author":"T Nishizeki","year":"2001","unstructured":"Nishizeki, T., Vygen, J., Zhou, X.: The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discret. Appl. Math. 115(1\u20133), 177\u2013186 (2001)","journal-title":"Discret. Appl. Math."},{"key":"14_CR43","unstructured":"Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In: Proceedings of the NeurIPS, pp. 9661\u20139670 (2018)"},{"key":"14_CR44","doi-asserted-by":"crossref","unstructured":"Rohatgi, D.: Near-optimal bounds for online caching with machine learned advice. In: Proceedings of the SODA, pp. 1834\u20131845 (2020)","DOI":"10.1137\/1.9781611975994.112"},{"key":"14_CR45","unstructured":"Wei, A., Zhang, F.: Optimal robustness-consistency trade-offs for learning-augmented online algorithms. In: Proceedings of the NeurIPS (2020)"},{"key":"14_CR46","unstructured":"Wei, A.: Better and simpler learning-augmented online caching. In: Proceedings of the APPROX\/RANDOM. LIPIcs, vol. 176, pp. 60:1\u201360:17 (2020)"},{"key":"14_CR47","doi-asserted-by":"crossref","unstructured":"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\u201310841 (2021)","DOI":"10.1609\/aaai.v35i12.17294"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-38906-1_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:06:51Z","timestamp":1690474011000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-38906-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031389054","9783031389061"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-38906-1_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"28 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Algorithms and Data Structures Symposium","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Montreal, QC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}