{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:23Z","timestamp":1750309523981,"version":"3.41.0"},"reference-count":95,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T00:00:00Z","timestamp":1747094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"German Science Foundation","award":["146371743 - TRR 89 Invasive Computing"],"award-info":[{"award-number":["146371743 - TRR 89 Invasive Computing"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            In non-clairvoyant scheduling, the task is to schedule jobs with a priori\n            <jats:italic>unknown<\/jats:italic>\n            processing requirements. We revisit this well-studied problem with the objective of minimizing the total (weighted) completion time in a recently popular learning-augmented setting that integrates possibly imperfect predictions into online algorithm design. While previous works used predictions on processing requirements, we propose a new prediction model that provides a relative order of jobs, which could be seen as predicting algorithmic actions rather than parts of the unknown input. We show that these succinct predictions have desired properties, admit a natural error measure, and enable algorithms with strong performance guarantees. Additionally, these predictions are learnable in both theory and practice. We generalize the algorithmic framework proposed in the seminal article by Purohit, Kumar, and Svitkina\u00a0(NeurIPS 2018) and present the first learning-augmented scheduling results for weighted jobs and unrelated machines. We demonstrate in empirical experiments the practicability and superior performance compared with the previously suggested single-machine algorithms.\n          <\/jats:p>","DOI":"10.1145\/3711872","type":"journal-article","created":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T11:19:16Z","timestamp":1736507956000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Permutation Predictions for Non-Clairvoyant Scheduling"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6714-5034","authenticated-orcid":false,"given":"Alexander","family":"Lindermayr","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Computer Science, University of Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3531-7644","authenticated-orcid":false,"given":"Nicole","family":"Megow","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computer Science, University of Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,5,13]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Lada A. Adamic and Bernardo A. Huberman. 2002. Zipf\u2019s law and the Internet. Glottometrics 2 2 (2002) 143\u2013150."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538306"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.97"},{"key":"e_1_3_2_5_2","series-title":"Proceedings of Machine Learning Research","first-page":"952","volume-title":"ICML","volume":"202","author":"Antoniadis Antonios","year":"2023","unstructured":"Antonios Antoniadis, Joan Boyar, Marek Eli\u00e1s, Lene Monrad Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, and Bertrand Simon. 2023. Paging with succinct predictions. In ICML(Proceedings of Machine Learning Research, Vol. 202). PMLR, 952\u2013968. Retrieved from https:\/\/proceedings.mlr.press\/v202\/antoniadis23a.html"},{"key":"e_1_3_2_6_2","first-page":"16714","volume-title":"NeurIPS","author":"Antoniadis Antonios","year":"2021","unstructured":"Antonios Antoniadis, Christian Coester, Marek Eli\u00e1s, Adam Polak, and Bertrand Simon. 2021. Learning-augmented dynamic power management with multiple states via new ski rental bounds. In NeurIPS. 16714\u201316726."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582689"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SWAT.2022.9"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451023"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.13"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ISAAC.2022.16"},{"key":"e_1_3_2_12_2","volume-title":"NeurIPS","author":"Bai Xingjian","year":"2023","unstructured":"Xingjian Bai and Christian Coester. 2023. Sorting with predictions. In NeurIPS."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2023.11"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-49815-2_6"},{"key":"e_1_3_2_15_2","volume-title":"NeurIPS","author":"Balkanski Eric","year":"2023","unstructured":"Eric Balkanski, No\u00e9mie P\u00e9rivier, Clifford Stein, and Hao-Ting Wei. 2023. Energy-efficient scheduling with predictions. In NeurIPS."},{"key":"e_1_3_2_16_2","volume-title":"NeurIPS","author":"Bamas \u00c9tienne","year":"2020","unstructured":"\u00c9tienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. 2020. Learning augmented energy minimization via speed scaling. In NeurIPS."},{"key":"e_1_3_2_17_2","volume-title":"NeurIPS","author":"Bamas \u00c9tienne","year":"2020","unstructured":"\u00c9tienne Bamas, Andreas Maggiori, and Ola Svensson. 2020. The primal-dual method for learning augmented algorithms. In NeurIPS."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.24963\/IJCAI.2022\/636"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ISAAC.2023.9"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/378420.378792"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.34"},{"key":"e_1_3_2_22_2","volume-title":"NeurIPS","author":"Benomar Ziyad","year":"2023","unstructured":"Ziyad Benomar and Vianney Perchet. 2023. Advice querying under budget constraint for online algorithms. In NeurIPS."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2021.28"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38906-1_14"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3056461"},{"key":"e_1_3_2_26_2","series-title":"Proceedings of Machine Learning Research","first-page":"3583","volume-title":"ICML","volume":"162","author":"Chen Justin Y.","year":"2022","unstructured":"Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. 2022. Faster fundamental graph algorithms via learned predictions. In ICML(Proceedings of Machine Learning Research, Vol. 162). PMLR, 3583\u20133602. Retrieved from https:\/\/proceedings.mlr.press\/v162\/chen22v.html"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2023.43"},{"key":"e_1_3_2_28_2","unstructured":"Vincent Cohen-Addad Tommaso d\u2019Orsi Anupam Gupta Euiwoong Lee and Debmalya Panigrahi. 2024. Max-cut with \\(\\epsilon\\) -accurate predictions. In NeurIPS."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.21497"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/90.650143"},{"key":"e_1_3_2_31_2","series-title":"Proceedings of Machine Learning Research","first-page":"7231","volume-title":"ICML","volume":"202","author":"Davies Sami","year":"2023","unstructured":"Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. 2023. Predictive flows for faster ford-fulkerson. In ICML(Proceedings of Machine Learning Research, Vol. 202). PMLR, 7231\u20137248. Retrieved from https:\/\/proceedings.mlr.press\/v202\/davies23b.html"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797315598"},{"key":"e_1_3_2_33_2","first-page":"10393","volume-title":"NeurIPS","author":"Dinitz Michael","year":"2021","unstructured":"Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. 2021. Faster matchings via learned duals. In NeurIPS. 10393\u201310406."},{"key":"e_1_3_2_34_2","volume-title":"NeurIPS","author":"Dinitz Michael","year":"2022","unstructured":"Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. 2022. Algorithms with prediction portfolios. In NeurIPS."},{"key":"e_1_3_2_35_2","series-title":"Proceedings of Machine Learning Research","first-page":"8078","volume-title":"AISTATS","volume":"206","author":"Drygala Marina","year":"2023","unstructured":"Marina Drygala, Sai Ganesh Nagarajan, and Ola Svensson. 2023. Online algorithms with costly predictions. In AISTATS(Proceedings of Machine Learning Research, Vol. 206). PMLR, 8078\u20138101. Retrieved from https:\/\/proceedings.mlr.press\/v206\/drygala23a.html"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942"},{"issue":"2","key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1287\/mnsc.11.2.268","article-title":"Bounds for the optimal scheduling of n jobs on m processors","volume":"11","author":"Eastman Willard L.","year":"1964","unstructured":"Willard L. Eastman, Shimon Even, and I. Martin Isaacs. 1964. Bounds for the optimal scheduling of n jobs on m processors. Management Science 11, 2 (1964), 268\u2013279.","journal-title":"Management Science"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V36I9.21208"},{"key":"e_1_3_2_39_2","unstructured":"Marek Eli\u00e1s Haim Kaplan Yishay Mansour and Shay Moran. 2024. Learning-augmented algorithms with explicit predictors. In NeurIPS."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2019.63"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538296"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.98"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1287\/MOOR.2019.0999"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1287\/MOOR.22.3.513"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/263326.263344"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2024.62"},{"key":"e_1_3_2_47_2","unstructured":"Sungjin Im Janardhan Kulkarni and Kamesh Munagala. [n.d.]. Retrieved from https:\/\/faculty.ucmerced.edu\/sim3\/papers\/jacm-psp-errata.txt. Erratum."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3136754"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.63"},{"key":"e_1_3_2_50_2","series-title":"Proceedings of Machine Learning Research","first-page":"9588","volume-title":"ICML","volume":"162","author":"Im Sungjin","year":"2022","unstructured":"Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. 2022. Parsimonious learning-augmented caching. In ICML(Proceedings of Machine Learning Research, Vol. 162). PMLR, 9588\u20139601. Retrieved from https:\/\/proceedings.mlr.press\/v162\/im22a.html"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3593969"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2015.474"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.DISOPT.2022.100753"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-32726-1_18"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977936.8"},{"key":"e_1_3_2_56_2","volume-title":"Approximation in Deterministic and Stochastic Machine Scheduling","author":"J\u00e4ger Sven Joachim","year":"2021","unstructured":"Sven Joachim J\u00e4ger. 2021. Approximation in Deterministic and Stochastic Machine Scheduling. Ph. D. Dissertation. Technical University of Berlin, Germany. Retrieved from https:\/\/nbn-resolving.org\/urn:nbn:de:101:1-2021080402181972706268"},{"key":"e_1_3_2_57_2","volume-title":"NeurIPS","author":"Khodak Misha","year":"2022","unstructured":"Misha Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. 2022. Learning predictions for algorithms with predictions. In NeurIPS."},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00231-X"},{"key":"e_1_3_2_59_2","first-page":"489","volume-title":"SIGMOD Conference","author":"Kraska Tim","year":"2018","unstructured":"Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The case for learned index structures. In SIGMOD Conference. ACM, 489\u2013504. DOI:10.1145\/3183713.3196909"},{"key":"e_1_3_2_60_2","volume-title":"Web Protocols and Practice\u2014HTTP\/1.1, Networking Protocols, Caching, and Traffic Measurement","author":"Krishnamurthy Balachander","year":"2001","unstructured":"Balachander Krishnamurthy and Jennifer Rexford. 2001. Web Protocols and Practice\u2014HTTP\/1.1, Networking Protocols, Caching, and Traffic Measurement. Addison-Wesley."},{"key":"e_1_3_2_61_2","series-title":"Proceedings of Machine Learning Research","first-page":"18563","volume-title":"ICML","volume":"202","author":"Lassota Alexandra Anna","year":"2023","unstructured":"Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schl\u00f6ter. 2023. Minimalistic predictions to schedule jobs with online precedence constraints. In ICML(Proceedings of Machine Learning Research, Vol. 202). PMLR, 18563\u201318583. Retrieved from https:\/\/proceedings.mlr.press\/v202\/lassota23a.html"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.114"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2021.59"},{"key":"e_1_3_2_64_2","series-title":"Proceedings of Machine Learning Research","first-page":"6523","volume-title":"ICML","volume":"139","author":"Li Shi","year":"2021","unstructured":"Shi Li and Jiayi Xian. 2021. Online unrelated machine load balancing with predictions revisited. In ICML(Proceedings of Machine Learning Research, Vol. 139). PMLR, 6523\u20136532. Retrieved from http:\/\/proceedings.mlr.press\/v139\/li21w.html"},{"key":"e_1_3_2_65_2","series-title":"Proceedings of Machine Learning Research","first-page":"13431","volume-title":"ICML","volume":"162","author":"Lin Honghao","year":"2022","unstructured":"Honghao Lin, Tian Luo, and David P. Woodruff. 2022. Learning augmented binary search trees. In ICML(Proceedings of Machine Learning Research, Vol. 162). PMLR, 13431\u201313440. Retrieved from https:\/\/proceedings.mlr.press\/v162\/lin22f.html"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538579"},{"key":"e_1_3_2_67_2","unstructured":"Alexander Lindermayr and Nicole Megow. 2024. Repository of papers on algorithms with predictions. Retrieved from http:\/\/algorithms-with-predictions.github.io\/. [Accessed: (July 4 2024)]."},{"key":"e_1_3_2_68_2","series-title":"Proceedings of Machine Learning Research","first-page":"21312","volume-title":"ICML","volume":"202","author":"Lindermayr Alexander","year":"2023","unstructured":"Alexander Lindermayr, Nicole Megow, and Martin Rapp. 2023. Speed-oblivious online scheduling: Knowing (precise) speeds is not necessary. In ICML(Proceedings of Machine Learning Research, Vol. 202). PMLR, 21312\u201321334. Retrieved from https:\/\/proceedings.mlr.press\/v202\/lindermayr23a.html"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2022.99"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447579"},{"key":"e_1_3_2_71_2","volume-title":"NeurIPS","author":"McCauley Samuel","year":"2023","unstructured":"Samuel McCauley, Benjamin Moseley, Aidin Niaparast, and Shikha Singh. 2023. Online list labeling with predictions. In NeurIPS."},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","unstructured":"Robert McNaughton. 1959. Scheduling with deadlines and loss functions. Management Science 6 1 (Oct. 1959) 1\u201312. DOI:10.1287\/mnsc.6.1.1","DOI":"10.1287\/mnsc.6.1.1"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77903-2_3"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.ORL.2003.11.008"},{"key":"e_1_3_2_75_2","series-title":"Dagstuhl Seminar Proceedings","volume-title":"Algorithms for Optimization with Incomplete Information","volume":"05031","author":"Megow Nicole","year":"2005","unstructured":"Nicole Megow, Marc Uetz, and Tjark Vredeveld. 2005. Models and algorithms for stochastic online scheduling. In Algorithms for Optimization with Incomplete Information(Dagstuhl Seminar Proceedings, Vol. 05031). IBFI, Schloss Dagstuhl, Germany. Retrieved from http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2005\/110"},{"key":"e_1_3_2_76_2","series-title":"Proceedings of Machine Learning Research","first-page":"24478","volume-title":"ICML","volume":"202","author":"Merlis Nadav","year":"2023","unstructured":"Nadav Merlis, Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, and Vianney Perchet. 2023. On preemption and learning in stochastic scheduling. In ICML(Proceedings of Machine Learning Research, Vol. 202). PMLR, 24478\u201324516. Retrieved from https:\/\/proceedings.mlr.press\/v202\/merlis23a.html"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2020.14"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976830.1"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108637435.037"},{"issue":"1","key":"e_1_3_2_80_2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0304-3975(94)90151-1","article-title":"Non-clairvoyant scheduling","volume":"130","author":"Motwani Rajeev","year":"1994","unstructured":"Rajeev Motwani, Steven J. Phillips, and Eric Torng. 1994. Non-clairvoyant scheduling. Theor. Comput. Sci. 130, 1 (1994), 17\u201347.","journal-title":"Theor. Comput. Sci."},{"key":"e_1_3_2_81_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-05921-6","volume-title":"Scheduling: Theory, Algorithms, and Systems (sixth ed.)","author":"Pinedo Michael L.","year":"2022","unstructured":"Michael L. Pinedo. 2022. Scheduling: Theory, Algorithms, and Systems (sixth ed.). Springer."},{"key":"e_1_3_2_82_2","volume-title":"Handbook of Scheduling","author":"Pruhs Kirk","year":"2004","unstructured":"Kirk Pruhs, Jir\u00ed Sgall, and Eric Torng. 2004. Online scheduling. In Handbook of Scheduling. Chapman and Hall\/CRC."},{"key":"e_1_3_2_83_2","first-page":"9684","volume-title":"NeurIPS","author":"Purohit Manish","year":"2018","unstructured":"Manish Purohit, Zoya Svitkina, and Ravi Kumar. 2018. Improving online algorithms via ML predictions. In NeurIPS. 9684\u20139693."},{"key":"e_1_3_2_84_2","volume-title":"ICLR","author":"Sadek Karim Abdel","year":"2024","unstructured":"Karim Abdel Sadek and Marek Eli\u00e1s. 2024. Algorithms for caching and MTS with reduced number of predictions. In ICLR. OpenReview.net. Retrieved from https:\/\/openreview.net\/forum?id=QuIiLSktO4"},{"key":"e_1_3_2_85_2","volume-title":"NeurIPS","author":"Sakaue Shinsaku","year":"2022","unstructured":"Shinsaku Sakaue and Taihei Oki. 2022. Discrete-convex-analysis-based framework for warm-starting algorithms with predictions. In NeurIPS."},{"issue":"2","key":"e_1_3_2_86_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/jos.93","article-title":"The power of  \\(\\alpha\\) -points in preemptive single machine scheduling","volume":"5","author":"Schulz Andreas S","year":"2002","unstructured":"Andreas S Schulz and Martin Skutella. 2002. The power of \\(\\alpha\\) -points in preemptive single machine scheduling. Journal of Scheduling 5, 2 (2002), 121\u2013133.","journal-title":"Journal of Scheduling"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199357078"},{"key":"e_1_3_2_88_2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/BFb0029570","volume-title":"Online Algorithms: The State of the Art","author":"Sgall J.","year":"1998","unstructured":"J. Sgall. 1998. On-line scheduling\u2014a survey. In Online Algorithms: The State of the Art, Amos Fiat and Gerhard J. Woeginger (Eds.). LNCS, Vol. 1442. Springer, Berlin, 196\u2013231."},{"key":"e_1_3_2_89_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding Machine Learning\u2014From Theory to Algorithms","author":"Shalev-Shwartz Shai","year":"2014","unstructured":"Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning\u2014From Theory to Algorithms. Cambridge University Press."},{"key":"e_1_3_2_90_2","doi-asserted-by":"publisher","DOI":"10.1007\/S10107-016-1004-8"},{"issue":"1","key":"e_1_3_2_91_2","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/nav.3800030106","article-title":"Various optimizers for single-stage production","volume":"3","author":"Smith Wayne E","year":"1956","unstructured":"Wayne E Smith et\u00a0al. 1956. Various optimizers for single-stage production. Naval Research Logistics Quarterly 3, 1-2 (1956), 59\u201366.","journal-title":"Naval Research Logistics Quarterly"},{"key":"e_1_3_2_92_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.126"},{"key":"e_1_3_2_93_2","volume-title":"NeurIPS","author":"Wei Alexander","year":"2020","unstructured":"Alexander Wei and Fred Zhang. 2020. Optimal robustness-consistency trade-offs for learning-augmented online algorithms. In NeurIPS."},{"key":"e_1_3_2_94_2","doi-asserted-by":"publisher","DOI":"10.24963\/IJCAI.2022\/81"},{"key":"e_1_3_2_95_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS55097.2022.00036"},{"key":"e_1_3_2_96_2","first-page":"413","volume-title":"ICAPS","author":"Zhao Tianming","year":"2022","unstructured":"Tianming Zhao, Wei Li, and Albert Y. Zomaya. 2022. Uniform machine scheduling with predictions. In ICAPS. AAAI Press, 413\u2013422. Retrieved from https:\/\/ojs.aaai.org\/index.php\/ICAPS\/article\/view\/19827"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711872","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3711872","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:09Z","timestamp":1750295889000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711872"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,13]]},"references-count":95,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3711872"],"URL":"https:\/\/doi.org\/10.1145\/3711872","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2025,5,13]]},"assertion":[{"value":"2024-07-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}