{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T03:04:12Z","timestamp":1771038252245,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T00:00:00Z","timestamp":1625529600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["1844939"],"award-info":[{"award-number":["1844939"]}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["1617653"],"award-info":[{"award-number":["1617653"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,6]]},"DOI":"10.1145\/3409964.3461790","type":"proceedings-article","created":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T19:07:02Z","timestamp":1625080022000},"page":"285-294","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Non-Clairvoyant Scheduling with Predictions"],"prefix":"10.1145","author":[{"given":"Sungjin","family":"Im","sequence":"first","affiliation":[{"name":"University of California, Merced, Merced, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahshid","family":"Montazer Qaem","sequence":"additional","affiliation":[{"name":"University of California, Merced, Merced, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manish","family":"Purohit","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,6]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Anders Aamand Piotr Indyk and Ali Vakilian. 2019. (Learned) frequency estimation algorithms under Zipfian distribution. arXiv:1908.05198."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnca.2017.01.016"},{"key":"e_1_3_2_1_3_1","unstructured":"Keerti Anand Rong Ge and Debmalya Panigrahi. 2020. Customizing ML predictions for online algorithms. In ICML. 303--313."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Spyros Angelopoulos Shahin Kamali and Kimia Shadkami. 2021. Online bin packing with predictions. arXiv:2102.03311.","DOI":"10.24963\/ijcai.2022\/635"},{"key":"e_1_3_2_1_5_1","unstructured":"Antonios Antoniadis Christian Coester Marek Elias Adam Polak and Bertrand Simon. 2020 a. Online Metric Algorithms with Untrusted Predictions. In ICML. 345--355."},{"key":"e_1_3_2_1_6_1","unstructured":"Antonios Antoniadis Themis Gouleakis Pieter Kleer and Pavel Kolev. 2020 b. Secretary and online matching problems with machine learned advice. In NeurIPS ."},{"key":"e_1_3_2_1_7_1","unstructured":"\u00c9 tienne Bamas Andreas Maggiori Lars Rohwedder and Ola Svensson. 2020 b. Learning augmented energy minimization via speed scaling. In NeurIPS ."},{"key":"e_1_3_2_1_8_1","unstructured":"\u00c9 tienne Bamas Andreas Maggiori and Ola Svensson. 2020 a. The primal-dual method for learning augmented algorithms. In NeurIPS ."},{"key":"e_1_3_2_1_9_1","unstructured":"Edith Cohen Ofir Geri and Rasmus Pagh. 2020. Composable sketches for functions of frequencies: Beyond the worst case. In ICML . 2057--2067."},{"key":"e_1_3_2_1_10_1","unstructured":"Sreenivas Gollapudi and Debmalya Panigrahi. 2019. Online algorithms for rent-or-buy with expert advice. In ICML. 2319--2327."},{"key":"e_1_3_2_1_11_1","unstructured":"Chen-Yu Hsu Piotr Indyk Dina Katabi and Ali Vakilian. 2019. Learning-based frequency estimation algorithms. In ICLR ."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3136754"},{"key":"e_1_3_2_1_13_1","volume-title":"Online algorithms for weighted paging with predictions. ICALP","author":"Jiang Zhihao","year":"2020","unstructured":"Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. 2020. Online algorithms for weighted paging with predictions. ICALP (2020), 69:1--69:18."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_3_2_1_15_1","volume-title":"Jeffrey Dean, and Neoklis Polyzotis.","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. 489--504."},{"key":"e_1_3_2_1_16_1","unstructured":"Ravi Kumar Manish Purohit and Zoya Svitkina. 2018. Improving online algorithms Using ML predictions. In NeurIPS . 9661--9670."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Silvio Lattanzi Thomas Lavastida Benjamin Moseley and Sergei Vassilvitskii. 2020. Online scheduling via learned weights. In SODA. 1859--1877.","DOI":"10.1137\/1.9781611975994.114"},{"key":"e_1_3_2_1_18_1","unstructured":"Thomas Lavastida Benjamin Moseley R. Ravi and Chenyang Xu. 2020. Learnable and instance-robust predictions for online matching flows and load balancing. arXiv:2011.11743."},{"key":"e_1_3_2_1_19_1","unstructured":"Thodoris Lykouris and Sergei Vassilvtiskii. 2018. Competitive caching with machine learned advice. In ICML. 3296--3305."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Andr\u00e9a Matsunaga and Jos\u00e9 AB Fortes. 2010. On the use of machine learning to predict the time and resources consumed by applications. In Cluster Cloud and Grid Computing . 495--504.","DOI":"10.1109\/CCGRID.2010.98"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher. 2018. A model for learned Bloom filters and optimizing by sandwiching. In NeurIPS . 464--473.","DOI":"10.1007\/978-1-4614-8265-9_751"},{"key":"e_1_3_2_1_22_1","first-page":"1","article-title":"Scheduling with predictions and the price of misprediction","volume":"14","author":"Mitzenmacher Michael","year":"2020","unstructured":"Michael Mitzenmacher. 2020. Scheduling with predictions and the price of misprediction. In ITCS . 14:1--14:18.","journal-title":"ITCS ."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90151-1"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/WORKS.2014.12"},{"key":"e_1_3_2_1_25_1","volume-title":"Handbook of Scheduling - Algorithms, Models, and Performance Analysis , , Joseph Y.-T","author":"Pruhs Kirk","unstructured":"Kirk Pruhs, Jir'i Sgall, and Eric Torng. 2004. Online Scheduling. In Handbook of Scheduling - Algorithms, Models, and Performance Analysis , , Joseph Y.-T. Leung (Ed.). Chapman and Hall\/CRC."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Dhruv Rohatgi. 2020. Near-Optimal Bounds for Online Caching with Machine Learned Advice. In SODA . 1834--1845.","DOI":"10.1137\/1.9781611975994.112"},{"key":"e_1_3_2_1_27_1","volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"Roughgarden Tim","unstructured":"Tim Roughgarden. 2020. Beyond the Worst-Case Analysis of Algorithms .Cambridge University Press."},{"key":"e_1_3_2_1_28_1","unstructured":"Kapil Vaidya Eric Knorr Tim Kraska and Michael Mitzenmacher. 2021. Partitioned learned Bloom filter. In ICLR ."}],"event":{"name":"SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures","location":"Virtual Event USA","acronym":"SPAA '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409964.3461790","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/abs\/10.1145\/3409964.3461790","content-type":"text\/html","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409964.3461790","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409964.3461790","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T22:17:05Z","timestamp":1755814625000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409964.3461790"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,6]]},"references-count":28,"alternative-id":["10.1145\/3409964.3461790","10.1145\/3409964"],"URL":"https:\/\/doi.org\/10.1145\/3409964.3461790","relation":{},"subject":[],"published":{"date-parts":[[2021,7,6]]},"assertion":[{"value":"2021-07-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}