{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:59Z","timestamp":1750309319780,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,29]],"date-time":"2023-12-29T00:00:00Z","timestamp":1703808000000},"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,12,29]]},"abstract":"<jats:p>In this column, we will discuss some papers in online algorithms that appeared in 2023. 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\/3639528.3639538","type":"journal-article","created":{"date-parts":[[2024,1,3]],"date-time":"2024-01-03T23:09:52Z","timestamp":1704323392000},"page":"108-125","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["SIGACT News Online Algorithms Column 41: 2023 in review"],"prefix":"10.1145","volume":"54","author":[{"given":"Aflatoun","family":"Amouzandeh","sequence":"first","affiliation":[{"name":"University of Siegen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00f6ren","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":[[2024,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch69"},{"key":"e_1_2_1_2_1","first-page":"1","volume-title":"28th Annual European Symposium on Algorithms, ESA 2020, September 7--9, 2020, Pisa, Italy (Virtual Conference)","volume":"173","author":"Azar Yossi","year":"2020","unstructured":"Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou. Set cover with delay - clairvoyance is not required. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7--9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 8:1--8:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2020."},{"key":"e_1_2_1_3_1","first-page":"1","volume-title":"The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019","author":"Azar Yossi","year":"2019","unstructured":"Yossi Azar, Yuval Emek, Rob van Stee, and Danny Vainstein. The price of clustering in bin-packing with applications to bin-packingwith delays. In Christian Scheideler and Petra Berenbrink, editors, The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22--24, 2019, pages 1--10. ACM, 2019."},{"key":"e_1_2_1_4_1","first-page":"551","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19--23, 2017","author":"Azar Yossi","year":"2017","unstructured":"Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi. Online service with delay. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19--23, 2017, pages 551--563. ACM, 2017."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00013"},{"key":"e_1_2_1_6_1","first-page":"1","volume-title":"31st Annual European Symposium on Algorithms, ESA 2023, September 4--6","volume":"274","author":"Bampis Evripidis","year":"2023","unstructured":"Evripidis Bampis, Bruno Escoffier, Themis Gouleakis, Niklas Hahn, Kostas Lakis, Golnoosh Shahkarami, and Michalis Xefteris. Learning-augmented online TSP on rings, trees, flowers and (almost) everywhere else. In Inge Li G\u00f8rtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4--6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 12:1--12:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01576-0"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585132"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634180"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch78"},{"key":"e_1_2_1_12_1","first-page":"1","volume-title":"31st Annual European Symposium on Algorithms, ESA 2023, September 4--6","volume":"274","author":"Bullinger Martin","year":"2023","unstructured":"Martin Bullinger and Ren\u00b4e Romen. Online coalition formation under random arrival or coalition dissolution. In Inge Li G\u00f8rtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4--6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 27:1--27:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch57"},{"key":"e_1_2_1_14_1","volume-title":"A general framework for learning-augmented online allocation. arXiv preprint arXiv:2305.18861","author":"Cohen Ilan Reuven","year":"2023","unstructured":"Ilan Reuven Cohen and Debmalya Panigrahi. A general framework for learning-augmented online allocation. arXiv preprint arXiv:2305.18861, 2023."},{"key":"e_1_2_1_15_1","first-page":"1","volume-title":"31st Annual European Symposium on Algorithms, ESA 2023, September 4--6","volume":"274","author":"Cohen Ilan Reuven","year":"2023","unstructured":"Ilan Reuven Cohen and Binghui Peng. Primal-dual schemes for online matching in bounded degree graphs. In Inge Li G\u00f8rtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4--6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 35:1--35:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_16_1","first-page":"686","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023","author":"Jos\u00b4e","year":"2023","unstructured":"Jos\u00b4e R. Correa and Andr\u00b4es Cristi. A constant factor prophet inequality for online combinatorial auctions. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20--23, 2023, pages 686--697. ACM, 2023."},{"key":"e_1_2_1_17_1","unstructured":"Lindsey Deryckere and Seeun William Umboh. Online matching with set and concave delays. In Nicole Megow and Adam D. Smith editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM 2023 September 11--13 2023 Atlanta Georgia USA volume 275 of LIPIcs pages 17:1--17:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik 2023."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627824"},{"key":"e_1_2_1_19_1","first-page":"1","volume-title":"50th International Colloquium on Automata, Languages, and Programming, ICALP 2023","volume":"261","author":"Disser Yann","year":"2023","unstructured":"Yann Disser, Max Klimm, Kevin Schewior, and David Weckbecker. Incremental maximization via continuization. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10- 14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 47:1--47:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_20_1","first-page":"306","volume-title":"61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020","author":"D\u00a8utting Paul","year":"2020","unstructured":"Paul D\u00a8utting, Thomas Kesselheim, and Brendan Lucier. An o(log log m) prophet inequality for subadditive combinatorial auctions. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16--19, 2020, pages 306--317. IEEE, 2020."},{"key":"e_1_2_1_21_1","volume-title":"Online algorithms with randomly infused advice. arXiv preprint arXiv:2302.05366","author":"Emek Yuval","year":"2023","unstructured":"Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid. Online algorithms with randomly infused advice. arXiv preprint arXiv:2302.05366, 2023."},{"key":"e_1_2_1_22_1","volume-title":"Nikhil Bansal and Viswanath Nagarajan","author":"Ezra Tomer","year":"2023","unstructured":"Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. \"Who is next in line?\" on the significance of knowing the arrival order in bayesian online settings. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22--25, 2023, pages 3759--3776. SIAM, 2023."},{"key":"e_1_2_1_23_1","first-page":"1","volume-title":"50th International Colloquium on Automata, Languages, and Programming, ICALP 2023","volume":"261","author":"Feldman Michal","year":"2023","unstructured":"Michal Feldman, Federico Fusco, Simon Mauras, and Rebecca Reiffenh\u00a8auser. Truthful matching with online items and offline agents. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10--14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 58:1--58:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1226130"},{"key":"e_1_2_1_25_1","first-page":"1","volume-title":"31st Annual European Symposium on Algorithms, ESA 2023, September 4--6","volume":"274","author":"Ganz Amit","year":"2023","unstructured":"Amit Ganz, Pranav Nuti, and Roy Schwartz. A tight competitive ratio for online submodular welfare maximization. In Inge Li G\u00f8rtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4--6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 52:1--52:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_26_1","volume-title":"New mathematical diversions from Scientific American","author":"Gardner Martin","year":"1966","unstructured":"Martin Gardner. New mathematical diversions from Scientific American, chapter 3. Simon and Schuster, 1966. Reprint of the orgiinal column publisehd in February 1960 with additional comments."},{"key":"e_1_2_1_27_1","volume-title":"The cardinal complexity of online ordinal problems","author":"Gravin Nick","year":"2023","unstructured":"Nick Gravin, Enze Sun, and Zhihao Gavin Tang. The cardinal complexity of online ordinal problems, 2023. FOCS."},{"key":"e_1_2_1_28_1","first-page":"1","volume-title":"14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10--13","volume":"251","author":"Gupta Varun","year":"2023","unstructured":"Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep, and Janani Sundaresan. Look before, before you leap: Online vector load balancing with few reassignments. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10--13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 65:1--65:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.09.001"},{"key":"e_1_2_1_30_1","first-page":"1","volume-title":"31st Annual European Symposium on Algorithms, ESA 2023, September 4--6","volume":"274","author":"Hoefer Martin","year":"2023","unstructured":"Martin Hoefer and Kevin Schewior. Threshold testing and semi-online prophet inequalities. In Inge Li G\u00f8rtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4--6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 62:1--62:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_31_1","unstructured":"Sharat Ibrahimpur Manish Purohit Zoya Svitkina Erik Vee and Joshua R. Wang. Caching with reserves. In Amit Chakrabarti and Chaitanya Swamy editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM 2022 September 19--21 2022 University of Illinois Urbana-Champaign USA (Virtual Conference) volume 245 of LIPIcs pages 52:1--52:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik 2022."},{"key":"e_1_2_1_32_1","first-page":"1","volume-title":"50th International Colloquium on Automata, Languages, and Programming, ICALP 2023","volume":"261","author":"Ibrahimpur Sharat","year":"2023","unstructured":"Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua R. Wang. Efficient caching with reserves via marking. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10--14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 80:1--80:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_33_1","volume-title":"An optimal deterministic algorithm for online bmatching. Theor. Comput. Sci., 233(1--2):319--325","author":"Kalyanasundaram Bala","year":"2000","unstructured":"Bala Kalyanasundaram and Kirk Pruhs. An optimal deterministic algorithm for online bmatching. Theor. Comput. Sci., 233(1--2):319--325, 2000."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch56"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_2_1_36_1","volume-title":"Online and bandit algorithms beyond","author":"Kesselheim Thomas","year":"2023","unstructured":"Thomas Kesselheim, Marco Molinaro, and Sahil Singla. Online and bandit algorithms beyond p norms. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACMSIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22--25, 2023, pages 1566--1593. SIAM, 2023."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585222"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch59"},{"key":"e_1_2_1_39_1","volume-title":"Yixuan Even Xu, Yuhao Zhang, and Renfei Zhou. On the perturbation function of ranking and balance for weighted online bipartite matching","author":"Liang Jingxun","year":"2023","unstructured":"Jingxun Liang, Zhihao Gavin Tang, Yixuan Even Xu, Yuhao Zhang, and Renfei Zhou. On the perturbation function of ranking and balance for weighted online bipartite matching, 2023."},{"key":"e_1_2_1_40_1","volume-title":"Nikhil Bansal and Viswanath Nagarajan","author":"MacRury Calum","year":"2023","unstructured":"Calum MacRury, Will Ma, and Nathaniel Grammel. On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22--25, 2023, pages 1995--2014. SIAM, 2023."},{"key":"e_1_2_1_41_1","first-page":"1","volume-title":"50th International Colloquium on Automata, Languages, and Programming, ICALP 2023","volume":"261","author":"Mellou Konstantina","year":"2023","unstructured":"Konstantina Mellou, Marco Molinaro, and Rudy Zhou. Online demand scheduling with failovers. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10--14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 92:1--92:20. Schloss Dagstuhl - Leibniz- Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875567"},{"key":"e_1_2_1_43_1","first-page":"307","volume-title":"Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023","author":"Murhekar Aniket","year":"2023","unstructured":"Aniket Murhekar, David Arbour, Tung Mai, and Anup B. Rao. Brief announcement: Dynamic vector bin packing for online resource allocation in the cloud. In Kunal Agrawal and Julian Shun, editors, Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023, Orlando, FL, USA, June 17--19, 2023, pages 307--310. ACM, 2023."},{"key":"e_1_2_1_44_1","first-page":"1","article-title":"Near-optimum online ad allocation for targeted advertising","volume":"16","author":"Naor Joseph","year":"2018","unstructured":"Joseph (Seffi) Naor and David Wajc. Near-optimum online ad allocation for targeted advertising. ACM Trans. Economics and Comput., 6(3--4):16:1--16:20, 2018.","journal-title":"ACM Trans. Economics and Comput., 6(3--4)"},{"key":"e_1_2_1_45_1","unstructured":"Kalen Patton Matteo Russo and Sahil Singla. Submodular norms with applications to online facility location and stochastic probing. In Nicole Megow and Adam D. Smith editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM 2023 September 11--13 2023 Atlanta Georgia USA volume 275 of LIPIcs pages 23:1--23:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik 2023."},{"key":"e_1_2_1_46_1","first-page":"1","volume-title":"14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10--13","volume":"251","author":"Qiao Mingda","year":"2023","unstructured":"Mingda Qiao and Gregory Valiant. Online pen testing. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10--13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 91:1--91:26. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_47_1","first-page":"1","volume-title":"31st Annual European Symposium on Algorithms, ESA 2023, September 4--6","volume":"274","author":"Sun Enze","year":"2023","unstructured":"Enze Sun, Zonghan Yang, and Yuhao Zhang. Improved algorithms for online rent minimization problem under unit-size jobs. In Inge Li G\u00f8rtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4--6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 97:1--97:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2023."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2002.1211"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585107"},{"key":"e_1_2_1_50_1","first-page":"1802","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023","author":"David","year":"2023","unstructured":"David P. Woodruff and Taisuke Yasuda. New subset selection algorithms for low rank approximation: Offline and online. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20--23, 2023, pages 1802--1813. ACM, 2023."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639528.3639538","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639528.3639538","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:56Z","timestamp":1750291436000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639528.3639538"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,29]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,29]]}},"alternative-id":["10.1145\/3639528.3639538"],"URL":"https:\/\/doi.org\/10.1145\/3639528.3639538","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2023,12,29]]},"assertion":[{"value":"2024-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}