{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:48Z","timestamp":1750220088943,"version":"3.41.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,12,20]],"date-time":"2021-12-20T00:00:00Z","timestamp":1639958400000},"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":[[2021,12,20]]},"abstract":"<jats:p>In this column, we will discuss some papers in online algorithms that appeared in 2021. 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\/3510382.3510396","type":"journal-article","created":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T18:15:15Z","timestamp":1641233715000},"page":"80-96","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["SIGACT News Online Algorithms Column 38"],"prefix":"10.1145","volume":"52","author":[{"given":"Felix","family":"Hohne","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":[[2022,1,3]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"3041","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Agrawal Kunal","year":"2021"},{"key":"e_1_2_1_2_1","unstructured":"Spyros\n      Angelopoulos\n    .\n  Online search with a hint\n  . In James R. Lee editor 12th Innovations in Theoretical Computer Science Conference ITCS \n  2021 January 6--8 2021 Virtual Conference volume \n  185\n   of \n  LIPIcs pages 51:1{51:\n  16\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  Spyros Angelopoulos. Online search with a hint. In James R. Lee editor 12th Innovations in Theoretical Computer Science Conference ITCS 2021 January 6--8 2021 Virtual Conference volume 185 of LIPIcs pages 51:1{51:16. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"key":"e_1_2_1_3_1","volume-title":"11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12--14","volume":"151","author":"Angelopoulos Spyros","year":"2020"},{"key":"e_1_2_1_4_1","unstructured":"Antonios\n      Antoniadis Matthias\n      Englert Nicolaos\n      Matsakis and \n      Pavel\n     Vesel--y.\n  Breaking the barrier of 2 for the competitiveness of Longest Queue Drop\n  . In Nikhil Bansal Emanuela Merelli and James Worrell editors 48th International Colloquium on Automata Languages and Programming ICALP \n  2021 July 12--16 2021 Glasgow Scotland (Virtual Conference) volume \n  198\n   of \n  LIPIcs pages 17:1{17:\n  20\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  Antonios Antoniadis Matthias Englert Nicolaos Matsakis and Pavel Vesel--y. Breaking the barrier of 2 for the competitiveness of Longest Queue Drop. In Nikhil Bansal Emanuela Merelli and James Worrell editors 48th International Colloquium on Automata Languages and Programming ICALP 2021 July 12--16 2021 Glasgow Scotland (Virtual Conference) volume 198 of LIPIcs pages 17:1{17:20. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00024"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.24"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451023"},{"key":"e_1_2_1_8_1","first-page":"320","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Azar Yossi","year":"2021"},{"key":"e_1_2_1_9_1","first-page":"2861","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Bansal Nikhil","year":"2021"},{"key":"e_1_2_1_10_1","first-page":"1152","volume-title":"Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020","author":"Bansal Nikhil","year":"2020"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461801"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90209-E"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976021.1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316342"},{"key":"e_1_2_1_15_1","first-page":"2842","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Bhattacharya Sayan","year":"2021"},{"key":"e_1_2_1_16_1","unstructured":"Marcin\n      Bienkowski Artur\n      Kraska and \n      Hsiang-Hsuan\n      Liu\n    .\n  Traveling repairperson unrelated machines and other stories about average completion times\n  . In Nikhil Bansal Emanuela Merelli and James Worrell editors 48th International Colloquium on Automata Languages and Programming ICALP \n  2021 July 12--16 2021 Glasgow Scotland (Virtual Conference) volume \n  198\n   of \n  LIPIcs pages 28:1{ 28:\n  20\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  Marcin Bienkowski Artur Kraska and Hsiang-Hsuan Liu. Traveling repairperson unrelated machines and other stories about average completion times. In Nikhil Bansal Emanuela Merelli and James Worrell editors 48th International Colloquium on Automata Languages and Programming ICALP 2021 July 12--16 2021 Glasgow Scotland (Virtual Conference) volume 198 of LIPIcs pages 28:1{ 28:20. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007621832648"},{"volume-title":"New competitiveness bounds for the shared memory switch. CoRR, abs\/1907.04399","year":"2019","author":"Bochkov Ivan A.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","unstructured":"S--ebastien Bubeck Niv\n      Buchbinder Christian\n      Coester and \n      Mark\n      Sellke\n    .\n  Metrical service systems with transformations\n  . In James R. Lee editor 12th Innovations in Theoretical Computer Science Conference ITCS \n  2021 January 6--8 2021 Virtual Conference volume \n  185\n   of \n  LIPIcs pages 21:1{21:\n  20\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  S--ebastien Bubeck Niv Buchbinder Christian Coester and Mark Sellke. Metrical service systems with transformations. In James R. Lee editor 12th Innovations in Theoretical Computer Science Conference ITCS 2021 January 6--8 2021 Virtual Conference volume 185 of LIPIcs pages 21:1{21:20. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"key":"e_1_2_1_20_1","first-page":"2104","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Rabani Yuval","year":"2021"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-73879-2_2"},{"key":"e_1_2_1_22_1","first-page":"1147","volume-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019","author":"Coester Christian","year":"2019"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00010"},{"key":"e_1_2_1_24_1","first-page":"1149","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Deng Yuan","year":"2021"},{"key":"e_1_2_1_25_1","unstructured":"Shahar\n      Dobzinski\n    .\n  Two randomized mechanisms for combinatorial auctions\n  . In Moses Charikar Klaus Jansen Omer Reingold and Jos--e D. P. Rolim editors Approximation Randomization and Combi- natorial Optimization. Algorithms and Techniques 10th International Workshop APPROX \n  2007 and 11th International Workshop RANDOM 2007 Princeton NJ USA August 20--22 2007 Proceedings volume \n  4627\n   of \n  Lecture Notes in Computer Science pages 89{\n  103\n  . Springer 2007. ACM SIGACT News 93 December 2021 vol. 52 no. 4  Shahar Dobzinski. Two randomized mechanisms for combinatorial auctions. In Moses Charikar Klaus Jansen Omer Reingold and Jos--e D. P. Rolim editors Approximation Randomization and Combi- natorial Optimization. Algorithms and Techniques 10th International Workshop APPROX 2007 and 11th International Workshop RANDOM 2007 Princeton NJ USA August 20--22 2007 Proceedings volume 4627 of Lecture Notes in Computer Science pages 89{103. Springer 2007. ACM SIGACT News 93 December 2021 vol. 52 no. 4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.56"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00037"},{"key":"e_1_2_1_28_1","unstructured":"Yuval\n      Emek Shay\n      Kutten and \n      Yangguang\n      Shi\n    .\n  Online paging with a vanishing regret\n  . In James R. Lee editor 12th Innovations in Theoretical Computer Science Conference ITCS \n  2021 January 6--8 2021 Virtual Conference volume \n  185\n   of \n  LIPIcs pages 67:1{67:\n  20\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  Yuval Emek Shay Kutten and Yangguang Shi. Online paging with a vanishing regret. In James R. Lee editor 12th Innovations in Theoretical Computer Science Conference ITCS 2021 January 6--8 2021 Virtual Conference volume 185 of LIPIcs pages 67:1{67:20. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210404"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00046"},{"key":"e_1_2_1_31_1","unstructured":"Yiding\n      Feng\n     and \n      Rad\n      Niazadeh\n    .\n  Batching and optimal multi-stage bipartite allocations (extended abstract)\n  . In James R. Lee editor 12th Innovations in Theoretical Computer Science Conference ITCS \n  2021 January 6--8 2021 Virtual Conference volume \n  185\n   of \n  LIPIcs pages 88:1{88:\n  1\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  Yiding Feng and Rad Niazadeh. Batching and optimal multi-stage bipartite allocations (extended abstract). In James R. Lee editor 12th Innovations in Theoretical Computer Science Conference ITCS 2021 January 6--8 2021 Virtual Conference volume 185 of LIPIcs pages 88:1{88:1. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"key":"e_1_2_1_32_1","unstructured":"Nick\n      Gravin Zhihao Gavin Tang and Kangning Wang. Online stochastic matching with edge arrivals\n  . In Nikhil Bansal Emanuela Merelli and James Worrell editors 48th International Colloquium on Automata Languages and Programming ICALP \n  2021 July 12--16 2021 Glasgow Scotland (Virtual Conference) volume \n  198\n   of \n  LIPIcs pages 74:1{74:\n  20\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  Nick Gravin Zhihao Gavin Tang and Kangning Wang. Online stochastic matching with edge arrivals. In Nikhil Bansal Emanuela Merelli and James Worrell editors 48th International Colloquium on Automata Languages and Programming ICALP 2021 July 12--16 2021 Glasgow Scotland (Virtual Conference) volume 198 of LIPIcs pages 74:1{74:20. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"key":"e_1_2_1_33_1","first-page":"58","volume-title":"Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '01","author":"Hahne Ellen L.","year":"2001"},{"key":"e_1_2_1_34_1","first-page":"2818","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Henzinger Monika","year":"2021"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322205.3311084"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451079"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461790"},{"issue":"1","key":"e_1_2_1_38_1","first-page":"52","article-title":"Efficient parallel algorithms for edge coloring problems","volume":"8","author":"Karlo Howard J.","year":"1987","journal-title":"J. Algorithms"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451033"},{"key":"e_1_2_1_40_1","unstructured":"William\n      Kuszmaul\n     and \n      Alek\n      Westover\n    .\n  The variable-processor cup game\n  . In James R. Lee editor 12th Innovations in Theoretical Computer Science Conference ITCS \n  2021 January 6--8 2021 Virtual Conference volume \n  185\n   of \n  LIPIcs pages 16:1{16:\n  20\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  William Kuszmaul and Alek Westover. The variable-processor cup game. In James R. Lee editor 12th Innovations in Theoretical Computer Science Conference ITCS 2021 January 6--8 2021 Virtual Conference volume 185 of LIPIcs pages 16:1{16:20. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"key":"e_1_2_1_41_1","unstructured":"Thomas\n      Lavastida Benjamin\n      Moseley R.\n      Ravi and \n      Chenyang\n      Xu\n    .\n  Learnable and instance-robust predictions for online matching ows and load balancing\n  . In Petra Mutzel Rasmus Pagh and Grzegorz Herman editors 29th Annual European Symposium on Algorithms ESA \n  2021 September 6--8 2021 Lisbon Portugal (Virtual Conference) volume \n  204\n   of \n  LIPIcs pages 59:1{59:\n  17\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  Thomas Lavastida Benjamin Moseley R. Ravi and Chenyang Xu. Learnable and instance-robust predictions for online matching ows and load balancing. In Petra Mutzel Rasmus Pagh and Grzegorz Herman editors 29th Annual European Symposium on Algorithms ESA 2021 September 6--8 2021 Lisbon Portugal (Virtual Conference) volume 204 of LIPIcs pages 59:1{59:17. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"volume-title":"32nd International Symposium on Algorithms and Computation (ISAAC 2021","year":"2021","author":"Liang Ya-Chun","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","first-page":"2287","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Mathieu Claire","year":"2021"},{"volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017","year":"2017","author":"Molinaro Marco","key":"e_1_2_1_44_1"},{"key":"e_1_2_1_45_1","first-page":"2829","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Nagarajan Viswanath","year":"2021"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.53"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405696"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467613"},{"key":"e_1_2_1_49_1","unstructured":"Enoch\n      Peserico\n     and \n      Michele\n      Scquizzato\n    .\n  Matching on the line admits no o(\n   p log n)-competitive algorithm. In Nikhil Bansal Emanuela Merelli and James Worrell editors 48th International Colloquium on Automata Languages and Programming ICALP \n  2021 July 12--16 2021 Glasgow Scotland (Vir- tual \n  Conference) volume \n  198\n   of \n  LIPIcs pages 103:1{103:\n  3\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  Enoch Peserico and Michele Scquizzato. Matching on the line admits no o( p log n)-competitive algorithm. In Nikhil Bansal Emanuela Merelli and James Worrell editors 48th International Colloquium on Automata Languages and Programming ICALP 2021 July 12--16 2021 Glasgow Scotland (Vir- tual Conference) volume 198 of LIPIcs pages 103:1{103:3. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"key":"e_1_2_1_50_1","first-page":"52","article-title":"Improving online algorithms via ML predictions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018","author":"Purohit Manish","year":"2021","journal-title":"ACM SIGACT News"},{"key":"e_1_2_1_51_1","volume-title":"34th International Symposium on Com- putational Geometry, SoCG 2018","volume":"99","author":"Raghvendra Sharath","year":"2018"},{"key":"e_1_2_1_52_1","unstructured":"Amin\n      Saberi\n     and \n      David\n      Wajc\n    .\n  The greedy algorithm is not optimal for on-line edge coloring\n  . In Nikhil Bansal Emanuela Merelli and James Worrell editors 48th International Colloquium on Automata Languages and Programming ICALP \n  2021 July 12--16 2021 Glasgow Scotland (Virtual Conference) volume \n  198\n   of \n  LIPIcs pages 109:1{109:\n  18\n  . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.  Amin Saberi and David Wajc. The greedy algorithm is not optimal for on-line edge coloring. In Nikhil Bansal Emanuela Merelli and James Worrell editors 48th International Colloquium on Automata Languages and Programming ICALP 2021 July 12--16 2021 Glasgow Scotland (Virtual Conference) volume 198 of LIPIcs pages 109:1{109:18. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021."},{"volume-title":"Making three out of two: Three-way online correlated selection. CoRR, abs\/2107.02605","year":"2021","author":"Shin Yongho","key":"e_1_2_1_53_1"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3510382.3510396","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3510382.3510396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:45Z","timestamp":1750183785000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3510382.3510396"}},"subtitle":["2021 in review"],"short-title":[],"issued":{"date-parts":[[2021,12,20]]},"references-count":53,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,20]]}},"alternative-id":["10.1145\/3510382.3510396"],"URL":"https:\/\/doi.org\/10.1145\/3510382.3510396","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2021,12,20]]},"assertion":[{"value":"2022-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}