{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:10Z","timestamp":1750220050584,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T00:00:00Z","timestamp":1677542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2023,2,28]]},"abstract":"<jats:p>In this column, we will discuss some papers in online algorithms that appeared in 2022. As usual, we make no claim at complete coverage here, and have instead made a selection. If we have unaccountably missed your favorite paper and you would like to write about it or about any other topic in online algorithms, please don't hesitate to contact us!<\/jats:p>","DOI":"10.1145\/3586165.3586177","type":"journal-article","created":{"date-parts":[[2023,3,1]],"date-time":"2023-03-01T23:07:16Z","timestamp":1677712036000},"page":"90-104","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["SIGACT News Online Algorithms Column 40"],"prefix":"10.1145","volume":"54","author":[{"given":"Aflatoun","family":"Amouzandeh","sequence":"first","affiliation":[{"name":"University of Siegen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soren","family":"Schmitt","sequence":"additional","affiliation":[{"name":"University of Siegen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rob","family":"van Stee","sequence":"additional","affiliation":[{"name":"University of Siegen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,3]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"3022","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021","author":"Agrawal Kunal","year":"2021","unstructured":"Kunal Agrawal , Michael A. Bender , Rathish Das , William Kuszmaul , Enoch Peserico , and Michele Scquizzato . Tight bounds for parallel paging and green paging. In D\u00b4aniel Marx, editor , Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021 , pages 3022 -- 3041 . SIAM, 2021 . Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato. Tight bounds for parallel paging and green paging. In D\u00b4aniel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 3022--3041. SIAM, 2021."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/3490148.3538577","volume-title":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","author":"Agrawal Kunal","year":"2022","unstructured":"Kunal Agrawal , Michael A. Bender , Rathish Das , William Kuszmaul , Enoch Peserico , and Michele Scquizzato . Online parallel paging with optimal makespan. In Kunal Agrawal and I-Ting Angelina Lee, editors , SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures , Philadelphia, PA, USA, July 11 - 14 , 2022 , pages 205 -- 216 . ACM, 2022. Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato. Online parallel paging with optimal makespan. In Kunal Agrawal and I-Ting Angelina Lee, editors, SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022, pages 205--216. ACM, 2022."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1137\/1.9781611977073.2","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Ahmadian Sara","year":"2022","unstructured":"Sara Ahmadian , Hossein Esfandiari , Vahab Mirrokni , and Binghui Peng . Robust load balancing with machine learned advice . In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 20 -- 34 . SIAM, 2022 . Sara Ahmadian, Hossein Esfandiari, Vahab Mirrokni, and Binghui Peng. Robust load balancing with machine learned advice. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 20--34. SIAM, 2022."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0953"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1109\/FOCS.2011.90","volume-title":"IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011","author":"Alaei Saeed","year":"2011","unstructured":"Saeed Alaei . Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. In Rafail Ostrovsky, editor , IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 , Palm Springs, CA, USA, October 22--25 , 2011 , pages 512 -- 521 . IEEE Computer Society, 2011. Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22--25, 2011, pages 512--521. IEEE Computer Society, 2011."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00844-5"},{"key":"e_1_2_1_7_1","first-page":"1","volume-title":"30th Annual European Symposium on Algorithms, ESA 2022, September 5--9","volume":"244","author":"Albers Susanne","year":"2022","unstructured":"Susanne Albers and Sebastian Schubert . Tight bounds for online matching in bounded-degree graphs with vertex capacities. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors , 30th Annual European Symposium on Algorithms, ESA 2022, September 5--9 , 2022 , Berlin\/Potsdam, Germany , volume 244 of LIPIcs, pages 4: 1 -- 4 :16. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2022. Susanne Albers and Sebastian Schubert. Tight bounds for online matching in bounded-degree graphs with vertex capacities. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5--9, 2022, Berlin\/Potsdam, Germany, volume 244 of LIPIcs, pages 4:1--4:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2022."},{"key":"e_1_2_1_8_1","first-page":"345","volume-title":"International Conference on Machine Learning","author":"Antoniadis Antonios","year":"2020","unstructured":"Antonios Antoniadis , Christian Coester , Marek Elias , Adam Polak , and Bertrand Simon . Online metric algorithms with untrusted predictions . In International Conference on Machine Learning , pages 345 -- 355 . PMLR, 2020 . Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In International Conference on Machine Learning, pages 345--355. PMLR, 2020."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"1273","DOI":"10.1137\/1.9781611977073.53","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Argue CJ","year":"2022","unstructured":"CJ Argue , Anupam Gupta , Marco Molinaro , and Sahil Singla . Robust secretary and prophet algorithms for packing integer programs . In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1273 -- 1297 . SIAM, 2022 . CJ Argue, Anupam Gupta, Marco Molinaro, and Sahil Singla. Robust secretary and prophet algorithms for packing integer programs. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1273--1297. SIAM, 2022."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1158513"},{"key":"e_1_2_1_11_1","first-page":"1","volume-title":"49th International Colloquium on Automata, Languages, and Programming, ICALP 2022","volume":"229","author":"Ayyadevara Nikhil","year":"2022","unstructured":"Nikhil Ayyadevara , Rajni Dabas , Arindam Khan , and K. V. N. Sreenivas . Near-optimal algorithms for stochastic online bin packing. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors , 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022 , July 4 --8 , 2022 , Paris, France, volume 229 of LIPIcs, pages 12: 1 -- 12 :20. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2022. Nikhil Ayyadevara, Rajni Dabas, Arindam Khan, and K. V. N. Sreenivas. Near-optimal algorithms for stochastic online bin packing. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4--8, 2022, Paris, France, volume 229 of LIPIcs, pages 12:1--12:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2022."},{"key":"e_1_2_1_12_1","first-page":"1","volume-title":"49th International Colloquium on Automata, Languages, and Programming, ICALP 2022","volume":"229","author":"Azar Yossi","year":"2022","unstructured":"Yossi Azar , Chay Machluf , Boaz Patt-Shamir , and Noam Touitou . Competitive vertex recoloring. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors , 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022 , July 4 --8 , 2022 , Paris, France, volume 229 of LIPIcs, pages 13: 1 -- 13 :20. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2022. Yossi Azar, Chay Machluf, Boaz Patt-Shamir, and Noam Touitou. Competitive vertex recoloring. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4--8, 2022, Paris, France, volume 229 of LIPIcs, pages 13:1--13:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2022."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1137\/1.9781611977073.3","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Azar Yossi","year":"2022","unstructured":"Yossi Azar , Debmalya Panigrahi , and Noam Touitou . Online graph algorithms with predictions . In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 35 -- 66 . SIAM, 2022 . Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 35--66. SIAM, 2022."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"1368","DOI":"10.1109\/FOCS46700.2020.00129","volume-title":"2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)","author":"Azar Yossi","year":"2020","unstructured":"Yossi Azar and Noam Touitou . Beyond tree embeddings--a deterministic framework for network design with deadlines or delay . In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 1368 -- 1379 . IEEE, 2020 . Yossi Azar and Noam Touitou. Beyond tree embeddings--a deterministic framework for network design with deadlines or delay. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1368--1379. IEEE, 2020."},{"key":"e_1_2_1_15_1","first-page":"3202","volume-title":"Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022","author":"Bamas Etienne","year":"2022","unstructured":"\u00b4 Etienne Bamas , Marina Drygala , and Andreas Maggiori . An improved analysis of greedy for online steiner forest. In Joseph (Seffi) Naor and Niv Buchbinder, editors , Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022 , pages 3202 -- 3229 . SIAM, 2022 . \u00b4Etienne Bamas, Marina Drygala, and Andreas Maggiori. An improved analysis of greedy for online steiner forest. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022, pages 3202--3229. SIAM, 2022."},{"issue":"4","key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1002\/rsa.20236","article-title":"Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models","volume":"33","author":"Bandyopadhyay Antar","year":"2008","unstructured":"Antar Bandyopadhyay and David Gamarnik . Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models . Random Structures & Algorithms , 33 ( 4 ): 452 -- 479 , 2008 . Antar Bandyopadhyay and David Gamarnik. Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models. Random Structures & Algorithms, 33(4):452--479, 2008.","journal-title":"Random Structures & Algorithms"},{"key":"e_1_2_1_17_1","first-page":"1","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Banerjee Siddhartha","year":"2022","unstructured":"Siddhartha Banerjee , Vasilis Gkatzelis , Artur Gorokh , and Billy Jin . Online nash social welfare maximization with predictions . In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1 -- 19 . SIAM, 2022 . Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1--19. SIAM, 2022."},{"key":"e_1_2_1_18_1","volume-title":"Learningaugmented weighted paging","author":"Bansal Nikhil","year":"2021","unstructured":"Nikhil Bansal , Christian Coester , Ravi Kumar , Manish Purohit , and Erik Vee . Learningaugmented weighted paging , 2021 . Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learningaugmented weighted paging, 2021."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90209-E"},{"key":"e_1_2_1_20_1","first-page":"1","volume-title":"On some combinatorial questions in finite-dimensional spaces. Linear algebra and its applications","author":"B\u00b4ar\u00b4any Imreh","year":"1981","unstructured":"Imreh B\u00b4ar\u00b4any and Victor Grinberg . On some combinatorial questions in finite-dimensional spaces. Linear algebra and its applications , pages 1 -- 9 , 1981 . Imreh B\u00b4ar\u00b4any and Victor Grinberg. On some combinatorial questions in finite-dimensional spaces. Linear algebra and its applications, pages 1--9, 1981."},{"key":"e_1_2_1_21_1","first-page":"78","volume-title":"A study of replacement algorithms for a virtual-storage computer","author":"Belady Laszlo A.","year":"1966","unstructured":"Laszlo A. Belady . A study of replacement algorithms for a virtual-storage computer . volume 5 , pages 78 -- 101 . IBM , 1966 . Laszlo A. Belady. A study of replacement algorithms for a virtual-storage computer. volume 5, pages 78--101. IBM, 1966."},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/978-3-030-92702-8_14","volume-title":"Approximation and Online Algorithms - 19th International Workshop, WAOA","author":"Bienkowski Marcin","year":"2021","unstructured":"Marcin Bienkowski , Martin B\u00a8ohm , Martin Kouteck\u00b4y , Thomas Rothvo\u00df , Jir\u00b4? Sgall, and Pavel Vesel\u00b4y . Improved analysis of online balanced clustering . In Jochen K\u00a8onemann and Britta Peis, editors, Approximation and Online Algorithms - 19th International Workshop, WAOA 2021 , Lisbon, Portugal, September 6--10, 2021, Revised Selected Papers, volume 12982 of Lecture Notes in Computer Science , pages 224 -- 233 . Springer , 2021. Marcin Bienkowski, Martin B\u00a8ohm, Martin Kouteck\u00b4y, Thomas Rothvo\u00df, Jir\u00b4? Sgall, and Pavel Vesel\u00b4y. Improved analysis of online balanced clustering. In Jochen K\u00a8onemann and Britta Peis, editors, Approximation and Online Algorithms - 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6--10, 2021, Revised Selected Papers, volume 12982 of Lecture Notes in Computer Science, pages 224--233. Springer, 2021."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007621832648"},{"key":"e_1_2_1_24_1","series-title":"LIPIcs","first-page":"1","volume-title":"Jakub Pawlewicz, and Anna Zych- Pawlewicz. Recoloring interval graphs with limited recourse budget","author":"Bosek Bartlomiej","year":"2020","unstructured":"Bartlomiej Bosek , Yann Disser , Andreas Emil Feldmann , Jakub Pawlewicz, and Anna Zych- Pawlewicz. Recoloring interval graphs with limited recourse budget . In Susanne Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020 , June 22- 24, 2020, T\u00b4orshavn, Faroe Islands , volume 162 of LIPIcs , pages 17: 1 -- 17 :23. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2020. Bartlomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, and Anna Zych- Pawlewicz. Recoloring interval graphs with limited recourse budget. In Susanne Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, June 22- 24, 2020, T\u00b4orshavn, Faroe Islands, volume 162 of LIPIcs, pages 17:1--17:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2020."},{"key":"e_1_2_1_25_1","first-page":"1","volume-title":"30th Annual European Symposium on Algorithms, ESA 2022, September 5--9","volume":"244","author":"Bosek Bartlomiej","year":"2022","unstructured":"Bartlomiej Bosek and Anna Zych-Pawlewicz . Dynamic coloring of unit interval graphs with limited recourse budget. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors , 30th Annual European Symposium on Algorithms, ESA 2022, September 5--9 , 2022 , Berlin\/Potsdam, Germany , volume 244 of LIPIcs, pages 25: 1 -- 25 :14. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2022. Bartlomiej Bosek and Anna Zych-Pawlewicz. Dynamic coloring of unit interval graphs with limited recourse budget. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5--9, 2022, Berlin\/Potsdam, Germany, volume 244 of LIPIcs, pages 25:1--25:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2022."},{"key":"e_1_2_1_26_1","volume-title":"Robust algorithms for the secretary problem. arXiv preprint arXiv:1911.07352","author":"Bradac Domagoj","year":"2019","unstructured":"Domagoj Bradac , Anupam Gupta , Sahil Singla , and Goran Zuzic . Robust algorithms for the secretary problem. arXiv preprint arXiv:1911.07352 , 2019 . Domagoj Bradac, Anupam Gupta, Sahil Singla, and Goran Zuzic. Robust algorithms for the secretary problem. arXiv preprint arXiv:1911.07352, 2019."},{"key":"e_1_2_1_27_1","volume-title":"49th International Colloquium on Automata, Languages, and Programming (ICALP 2022","author":"Chen Ryder","year":"2022","unstructured":"Ryder Chen , Jahanvi Khatkar , and Seeun William Umboh . Online weighted cardinality joint replenishment problem with delay. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00a8ur Informatik , 2022 . Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh. Online weighted cardinality joint replenishment problem with delay. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00a8ur Informatik, 2022."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1145\/3490148.3538567","volume-title":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","author":"Coester Christian","year":"2022","unstructured":"Christian Coester , Roie Levin , Joseph (Seffi) Naor , and Ohad Talmon . Competitive algorithms for block-aware caching. In Kunal Agrawal and I-Ting Angelina Lee, editors , SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures , Philadelphia, PA, USA, July 11 - 14 , 2022 , pages 161 -- 172 . ACM, 2022. Christian Coester, Roie Levin, Joseph (Seffi) Naor, and Ohad Talmon. Competitive algorithms for block-aware caching. In Kunal Agrawal and I-Ting Angelina Lee, editors, SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022, pages 161--172. ACM, 2022."},{"issue":"1","key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/BF02031749","article-title":"Heuristic procedures for a stochastic lot-sizing problem in make-to-order manufacturing","volume":"59","author":"Dellaert Nico P","year":"1995","unstructured":"Nico P Dellaert and M Teresa Melo . Heuristic procedures for a stochastic lot-sizing problem in make-to-order manufacturing . Annals of Operations Research , 59 ( 1 ): 227 -- 258 , 1995 . Nico P Dellaert and M Teresa Melo. Heuristic procedures for a stochastic lot-sizing problem in make-to-order manufacturing. Annals of Operations Research, 59(1):227--258, 1995.","journal-title":"Annals of Operations Research"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.272.0133"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80060-1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/FOCS.2019.00011","volume-title":"60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","author":"Gamlath Buddhima","year":"2019","unstructured":"Buddhima Gamlath , Michael Kapralov , Andreas Maggiori , Ola Svensson , and David Wajc . Online matching with general arrivals. In David Zuckerman, editor , 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 , Baltimore, Maryland, USA, November 9--12 , 2019 , pages 26 -- 37 . IEEE Computer Society, 2019. Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. Online matching with general arrivals. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9--12, 2019, pages 26--37. IEEE Computer Society, 2019."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"1356","DOI":"10.1137\/1.9781611977073.57","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Gupta Anupam","year":"2022","unstructured":"Anupam Gupta , Vijaykrishna Gurunathan , Ravishankar Krishnaswamy , Amit Kumar , and Sahil Singla . Online discrepancy with recourse for vectors and graphs . In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1356 -- 1383 . SIAM, 2022 . Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, and Sahil Singla. Online discrepancy with recourse for vectors and graphs. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1356--1383. SIAM, 2022."},{"key":"e_1_2_1_34_1","first-page":"589","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Gupta Anupam","year":"2017","unstructured":"Anupam Gupta , R Ravi , Kunal Talwar , and Seeun William Umboh . Last but not least: Online spanners for buy-at-bulk . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 589 -- 599 . SIAM, 2017 . Anupam Gupta, R Ravi, Kunal Talwar, and Seeun William Umboh. Last but not least: Online spanners for buy-at-bulk. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 589--599. SIAM, 2017."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510382.3510396"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/3519935.3520046","volume-title":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","author":"Huang Zhiyi","year":"2022","unstructured":"Zhiyi Huang , Xinkai Shu , and Shuyi Yan . The power of multiple choices in online stochastic matching. In Stefano Leonardi and Anupam Gupta, editors , STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing , Rome, Italy, June 20 - 24 , 2022 , pages 91 -- 103 . ACM, 2022. Zhiyi Huang, Xinkai Shu, and Shuyi Yan. The power of multiple choices in online stochastic matching. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 91--103. ACM, 2022."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399452"},{"key":"e_1_2_1_38_1","first-page":"1221","volume-title":"Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022","author":"Jiang Jiashuo","year":"2022","unstructured":"Jiashuo Jiang , Will Ma , and Jiawei Zhang . Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. In Joseph (Seffi) Naor and Niv Buchbinder, editors , Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022 , pages 1221 -- 1246 . SIAM, 2022 . Jiashuo Jiang, Will Ma, and Jiawei Zhang. Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022, pages 1221--1246. SIAM, 2022."},{"key":"e_1_2_1_39_1","first-page":"1247","volume-title":"Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022","author":"Kaplan Haim","year":"2022","unstructured":"Haim Kaplan , David Naori , and Danny Raz . Online weighted matching with a sample. In Joseph (Seffi) Naor and Niv Buchbinder, editors , Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022 , pages 1247 -- 1272 . SIAM, 2022 . Haim Kaplan, David Naori, and Danny Raz. Online weighted matching with a sample. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022, pages 1247--1272. SIAM, 2022."},{"key":"e_1_2_1_40_1","volume-title":"Knapsack secretary with bursty adversary. arXiv preprint arXiv:2006.11607","author":"Kesselheim Thomas","year":"2020","unstructured":"Thomas Kesselheim and Marco Molinaro . Knapsack secretary with bursty adversary. arXiv preprint arXiv:2006.11607 , 2020 . Thomas Kesselheim and Marco Molinaro. Knapsack secretary with bursty adversary. arXiv preprint arXiv:2006.11607, 2020."},{"key":"e_1_2_1_41_1","first-page":"329","volume-title":"Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022","author":"Klimm Max","year":"2022","unstructured":"Max Klimm , Guillaume Sagnol , Martin Skutella , and Khai Van Tran . Competitive strategies for symmetric rendezvous on the line. In Joseph (Seffi) Naor and Niv Buchbinder, editors , Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022 , pages 329 -- 347 . SIAM, 2022 . Max Klimm, Guillaume Sagnol, Martin Skutella, and Khai Van Tran. Competitive strategies for symmetric rendezvous on the line. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022, pages 329--347. SIAM, 2022."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1145\/3519935.3519986","volume-title":"Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing","author":"Kulkarni Janardhan","year":"2022","unstructured":"Janardhan Kulkarni , Yang P Liu , Ashwin Sah , Mehtaab Sawhney , and Jakub Tarnawski . Online edge coloring via tree recurrences and correlation decay . In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 104 -- 116 , 2022 . Janardhan Kulkarni, Yang P Liu, Ashwin Sah, Mehtaab Sawhney, and Jakub Tarnawski. Online edge coloring via tree recurrences and correlation decay. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 104--116, 2022."},{"key":"e_1_2_1_43_1","first-page":"1","volume-title":"49th International Colloquium on Automata, Languages, and Programming, ICALP 2022","volume":"229","author":"Kuszmaul William","year":"2022","unstructured":"William Kuszmaul and Shyam Narayanan . Optimal time-backlog tradeoffs for the variableprocessor cup game. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors , 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022 , July 4 --8 , 2022 , Paris, France, volume 229 of LIPIcs, pages 85: 1 -- 85 :20. Schloss Dagstuhl - Leibniz- Zentrum f\u00a8ur Informatik, 2022. William Kuszmaul and Shyam Narayanan. Optimal time-backlog tradeoffs for the variableprocessor cup game. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4--8, 2022, Paris, France, volume 229 of LIPIcs, pages 85:1--85:20. Schloss Dagstuhl - Leibniz- Zentrum f\u00a8ur Informatik, 2022."},{"key":"e_1_2_1_44_1","volume-title":"Competitive caching with machine learned advice. CoRR, abs\/1802.05399","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvitskii . Competitive caching with machine learned advice. CoRR, abs\/1802.05399 , 2018 . Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. CoRR, abs\/1802.05399, 2018."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2013.2272252"},{"key":"e_1_2_1_46_1","first-page":"1","volume-title":"30th Annual European Symposium on Algorithms, ESA 2022, September 5--9","volume":"244","author":"Rajaraman Rajmohan","year":"2022","unstructured":"Rajmohan Rajaraman and Omer Wasim . Improved bounds for online balanced graph repartitioning. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors , 30th Annual European Symposium on Algorithms, ESA 2022, September 5--9 , 2022 , Berlin\/Potsdam, Germany , volume 244 of LIPIcs, pages 83: 1 -- 83 :15. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2022. Rajmohan Rajaraman and Omer Wasim. Improved bounds for online balanced graph repartitioning. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5--9, 2022, Berlin\/Potsdam, Germany, volume 244 of LIPIcs, pages 83:1--83:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2022."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","first-page":"1834","DOI":"10.1137\/1.9781611975994.112","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Rohatgi Dhruv","year":"2020","unstructured":"Dhruv Rohatgi . Near-optimal bounds for online caching with machine learned advice . In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1834 -- 1845 . SIAM, 2020 . Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1834--1845. SIAM, 2020."},{"issue":"5","key":"e_1_2_1_48_1","first-page":"1897","article-title":"Uniqueness thresholds on trees versus graphs","volume":"18","author":"Sly Allan","year":"2008","unstructured":"Allan Sly . Uniqueness thresholds on trees versus graphs . The Annals of Applied Probability , 18 ( 5 ): 1897 -- 1909 , 2008 . Allan Sly. Uniqueness thresholds on trees versus graphs. The Annals of Applied Probability, 18(5):1897--1909, 2008.","journal-title":"The Annals of Applied Probability"},{"key":"e_1_2_1_49_1","first-page":"1","volume-title":"32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6--8","volume":"212","author":"Touitou Noam","year":"2021","unstructured":"Noam Touitou . Nearly-tight lower bounds for set cover and network design with deadlines\/ delay. In Hee-Kap Ahn and Kunihiko Sadakane, editors , 32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6--8 , 2021 , Fukuoka, Japan , volume 212 of LIPIcs, pages 53: 1 -- 53 :16. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2021. Noam Touitou. Nearly-tight lower bounds for set cover and network design with deadlines\/ delay. In Hee-Kap Ahn and Kunihiko Sadakane, editors, 32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6--8, 2021, Fukuoka, Japan, volume 212 of LIPIcs, pages 53:1--53:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2021."},{"key":"e_1_2_1_50_1","unstructured":"Alexander\n      Wei\n    .\n  Better and simpler learning-augmented online caching\n  . In Jaroslaw Byrka and Raghu Meka editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM \n  2020 August 17--19 2020 Virtual Conference volume \n  176\n   of \n  LIPIcs pages 60:\n  1\n  --\n  60\n  :17. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur \n  Informatik 2020.  Alexander Wei. Better and simpler learning-augmented online caching. In Jaroslaw Byrka and Raghu Meka editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM 2020 August 17--19 2020 Virtual Conference volume 176 of LIPIcs pages 60:1--60:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik 2020."},{"key":"e_1_2_1_51_1","first-page":"140","volume-title":"Proceedings of the thirtyeighth annual ACM symposium on Theory of computing","author":"Weitz Dror","year":"2006","unstructured":"Dror Weitz . Counting independent sets up to the tree threshold . In Proceedings of the thirtyeighth annual ACM symposium on Theory of computing , pages 140 -- 149 , 2006 . Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the thirtyeighth annual ACM symposium on Theory of computing, pages 140--149, 2006."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3586165.3586177","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3586165.3586177","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:12Z","timestamp":1750183692000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3586165.3586177"}},"subtitle":["2022 in review"],"short-title":[],"issued":{"date-parts":[[2023,2,28]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2,28]]}},"alternative-id":["10.1145\/3586165.3586177"],"URL":"https:\/\/doi.org\/10.1145\/3586165.3586177","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2023,2,28]]},"assertion":[{"value":"2023-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}