{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:25:08Z","timestamp":1750220708819,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T00:00:00Z","timestamp":1575417600000},"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":[[2019,12,4]]},"abstract":"<jats:p>In this column, we will discuss some papers in online algorithms that appeared in 2019. 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\/3374857.3374871","type":"journal-article","created":{"date-parts":[[2019,12,5]],"date-time":"2019-12-05T14:07:24Z","timestamp":1575554844000},"page":"77-92","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["SIGACT News Online Algorithms Column 35"],"prefix":"10.1145","volume":"50","author":[{"given":"Felix","family":"H\u00f6hne","sequence":"first","affiliation":[{"name":"University of Siegen, Siegen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00f6ren","family":"Schmitt","sequence":"additional","affiliation":[{"name":"University of Siegen, Siegen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rob","family":"van Stee","sequence":"additional","affiliation":[{"name":"University of Siegen, Siegen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,12,4]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"17","volume-title":"36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz Interna- tional Proceedings in Informatics (LIPIcs)","author":"Angelopoulos Spyros","year":"2019"},{"first-page":"122","volume-title":"Chan [19]","author":"Argue C. J.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46541-3_53"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329573"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323180"},{"volume-title":"General framework for metric optimization problems with delay or with deadlines. CoRR, abs\/1904.07131","year":"2019","author":"Azar Yossi","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","volume":"132","author":"Baier Christel","year":"2019"},{"key":"e_1_2_1_8_1","first-page":"14","volume-title":"27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Bampis Evripidis","year":"2019"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.81"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.64"},{"key":"e_1_2_1_11_1","volume-title":"27th Annual European Symposium on Algorithms, ESA 2019, September 9--11","volume":"144","author":"Berndt Sebastian","year":"2019"},{"volume-title":"Slaying hydrae: Improved bounds for generalized k-server in uniform metrics. CoRR, abs\/1810.00580","year":"2018","author":"Bienkowski Marcin","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","first-page":"17","volume-title":"36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Birx Alexander","year":"2019"},{"key":"e_1_2_1_14_1","unstructured":"Alexander\n      Birx Yann\n      Disser and \n      Kevin\n      Schewior\n    .\n  Improved Bounds for Open Online Dial-a- Ride on the Line\n  . In Dimitris Achlioptas and L--aszl--o A. V--egh editors Approximation Random-\n   ization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM \n  2019\n  ) volume \n  145\n   of \n  Leibniz International Proceedings in Informatics (LIPIcs) pages 21:1{ 21:\n  22 Dagstuhl Germany 2019. Schloss Dagstuhl{Leibniz-Zentrum fuer \n  Informatik\n  .  Alexander Birx Yann Disser and Kevin Schewior. Improved Bounds for Open Online Dial-a- Ride on the Line. In Dimitris Achlioptas and L--aszl--o A. V--egh editors Approximation Random- ization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2019) volume 145 of Leibniz International Proceedings in Informatics (LIPIcs) pages 21:1{ 21:22 Dagstuhl Germany 2019. Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik."},{"first-page":"238","volume-title":"Friggstad et al. [29]","author":"Boyar Joan","key":"e_1_2_1_15_1"},{"first-page":"16","volume-title":"James R. Lee, and Aleksander Madry. k-server via multiscale entropic regularization. In Diakonikolas et al. [24]","author":"Cohen Michael B.","key":"e_1_2_1_16_1"},{"volume-title":"Yuanzhi Li, and Mark Sellke. Competitively chasing convex bodies. In Charikar and Cohen [20]","key":"e_1_2_1_17_1","first-page":"868"},{"first-page":"116","volume-title":"Chan [19]","author":"Buchbinder Niv","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276"},{"first-page":"1981","volume-title":"Chan [19]","author":"Chawla Shuchi","key":"e_1_2_1_21_1"},{"first-page":"1147","volume-title":"Charikar and Cohen 20","author":"Coester Christian","key":"e_1_2_1_22_1"},{"volume-title":"Tight bounds for online edge coloring. CoRR, abs\/1904.09222","year":"2019","author":"Cohen Ilan Reuven","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745"},{"key":"e_1_2_1_25_1","unstructured":"Yuval\n      Emek Adam\n      Goldbraikh and \n      Erez\n      Kantor\n    .\n  Online Disjoint Set Cover Without Prior Knowledge\n  . In Michael A. Bender Ola Svensson and Grzegorz Herman editors 27th Annual European Symposium on Algorithms (ESA \n  2019\n  ) volume \n  144\n   of \n  Leibniz International Proceed- ings in Informatics (LIPIcs) pages 44:1{44:\n  16 Dagstuhl Germany 2019. Schloss Dagstuhl{ Leibniz-Zentrum fuer \n  Informatik\n  .  Yuval Emek Adam Goldbraikh and Erez Kantor. Online Disjoint Set Cover Without Prior Knowledge. In Michael A. Bender Ola Svensson and Grzegorz Herman editors 27th Annual European Symposium on Algorithms (ESA 2019) volume 144 of Leibniz International Proceed- ings in Informatics (LIPIcs) pages 44:1{44:16 Dagstuhl Germany 2019. Schloss Dagstuhl{ Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_26_1","first-page":"399","volume-title":"30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013","volume":"20","author":"Epstein Leah","year":"2013"},{"first-page":"379","volume-title":"Friggstad et al. [29]","author":"Fekete P.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189324"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24766-9"},{"volume-title":"Online matching with general arrivals. CoRR, abs\/1904.08255","year":"2019","author":"Gamlath Buddhima","key":"e_1_2_1_30_1"},{"first-page":"14","volume-title":"Baier et al. [7]","author":"Garg Naveen","key":"e_1_2_1_31_1"},{"first-page":"422","volume-title":"Friggstad et al. [29]","author":"Golan Shay","key":"e_1_2_1_32_1"},{"first-page":"14","volume-title":"Baier et al. [7]","author":"Gupta Anupam","key":"e_1_2_1_33_1"},{"first-page":"156","volume-title":"Chan [19]","author":"Gupta Anupam","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","first-page":"694","volume-title":"Proceedings of the 41st Annual ACM Sym- posium on Theory of Computing, STOC 2009","author":"Gupta Anupam","year":"2009"},{"volume-title":"30th International Symposium on Algorithms and Computation (ISAAC 2019)","year":"2019","author":"Han Xin","key":"e_1_2_1_36_1"},{"first-page":"29","volume-title":"Xiaowei Wu, Yuhao Zhang, and Xue Zhu. How to match when all vertices arrive online. In Diakonikolas et al. [24]","author":"Huang Zhiyi","key":"e_1_2_1_37_1"},{"first-page":"2886","volume-title":"Runzhou Tao, XiaoweiWu, and Yuhao Zhang. Tight competitive ratios of classic matching algorithms in the fully online model. In Chan [19]","author":"Huang Zhiyi","key":"e_1_2_1_38_1"},{"volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13--17, 1990","year":"1990","author":"Karp Richard M.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_50"},{"volume-title":"Technische Universitat Berlin","year":"2002","author":"Krumke Sven Oliver","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","volume-title":"10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10--12","volume":"124","author":"Kumar Ravi","year":"2019"},{"key":"e_1_2_1_44_1","first-page":"14","volume-title":"36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Luo Kelin","year":"2019"},{"first-page":"14","volume-title":"Baier et al. [7]","author":"Naor Joseph","key":"e_1_2_1_45_1"},{"volume-title":"30th International Symposium on Algorithms and Computation (ISAAC 2019)","year":"2019","author":"Naori David","key":"e_1_2_1_46_1"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218497"},{"key":"e_1_2_1_48_1","first-page":"18","volume-title":"36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Peserico Enoch","year":"2019"},{"key":"e_1_2_1_49_1","unstructured":"Sharath\n      Raghvendra\n    .\n  A robust and optimal online algorithm for minimum metric bipartite matching\n  . In Klaus Jansen Claire Mathieu Jos--e D. P. Rolim and Chris Umans editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM \n  2016 September 7--9 2016 Paris France volume \n  60\n   of \n  LIPIcs pages 18:1{18:\n  16\n  . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2016.  Sharath Raghvendra. A robust and optimal online algorithm for minimum metric bipartite matching. In Klaus Jansen Claire Mathieu Jos--e D. P. Rolim and Chris Umans editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM 2016 September 7--9 2016 Paris France volume 60 of LIPIcs pages 18:1{18:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2016."},{"first-page":"1993","volume-title":"Chan [19]","author":"Reienhauser Rebecca","key":"e_1_2_1_50_1"},{"first-page":"142","volume-title":"Chan [19]","author":"Pavel","key":"e_1_2_1_51_1"},{"key":"e_1_2_1_52_1","unstructured":"Yajun\n      Wang\n     and \n      Sam\n       Chiu-wai \n      Wong\n    .\n  Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm\n  . In Magn--us M. Halld--orsson Kazuo Iwama Naoki Kobayashi and Bettina Speckmann editors Automata Languages and Programming - 42nd International Colloquium ICALP \n  2015 Kyoto Japan July 6--10 2015 Proceedings Part I volume \n  9134\n   of \n  Lecture Notes in Computer Science pages 1070{\n  1081\n  . Springer 2015.  Yajun Wang and Sam Chiu-wai Wong. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In Magn--us M. Halld--orsson Kazuo Iwama Naoki Kobayashi and Bettina Speckmann editors Automata Languages and Programming - 42nd International Colloquium ICALP 2015 Kyoto Japan July 6--10 2015 Proceedings Part I volume 9134 of Lecture Notes in Computer Science pages 1070{1081. Springer 2015."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3374857.3374871","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3374857.3374871","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:08Z","timestamp":1750199588000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3374857.3374871"}},"subtitle":["2019 in review"],"short-title":[],"issued":{"date-parts":[[2019,12,4]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,4]]}},"alternative-id":["10.1145\/3374857.3374871"],"URL":"https:\/\/doi.org\/10.1145\/3374857.3374871","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2019,12,4]]},"assertion":[{"value":"2019-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}