{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:49Z","timestamp":1750220509626,"version":"3.41.0"},"reference-count":102,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,1,2]],"date-time":"2021-01-02T00:00:00Z","timestamp":1609545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Det Frie Forskningsr\u00e5d","award":["DFF-7014-00041"],"award-info":[{"award-number":["DFF-7014-00041"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>The standard measure for the quality of online algorithms is the competitive ratio. This measure is generally applicable, and for some problems it works well, but for others it fails to distinguish between algorithms that have very different performance. Thus, ever since its introduction, researchers have worked on improving the measure, defining variants, or defining measures based on other concepts to improve on the situation. Relative worst-order analysis (RWOA) is one of the most thoroughly tested such proposals. With RWOA, many separations of algorithms not obtainable with competitive analysis have been found.<\/jats:p>\n          <jats:p>In RWOA, two algorithms are compared directly, rather than indirectly as is done in competitive analysis, where both algorithms are compared separately to an optimal offline algorithm. If, up to permutations of the request sequences, one algorithm is always at least as good and sometimes better than another, then the first algorithm is deemed the better algorithm by RWOA.<\/jats:p>\n          <jats:p>We survey the most important results obtained with this technique and compare it with other quality measures. The survey includes a quite complete set of references.<\/jats:p>","DOI":"10.1145\/3425910","type":"journal-article","created":{"date-parts":[[2021,1,2]],"date-time":"2021-01-02T17:08:21Z","timestamp":1609607301000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Relative Worst-order Analysis"],"prefix":"10.1145","volume":"54","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[{"name":"University of Southern Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[{"name":"University of Southern Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0560-3794","authenticated-orcid":false,"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[{"name":"University of Southern Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,1,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794277858"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.08.002"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3288645.3288674"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.11.005"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00142-Y"},{"volume-title":"Online Algorithms\u2014The State of the Art, Amos Fiat and Gerhard J","author":"Albers Susanne","key":"e_1_2_1_6_1","unstructured":"Susanne Albers and Jeffrey Westbrook . 1998. Self-organizing data structures . In Online Algorithms\u2014The State of the Art, Amos Fiat and Gerhard J . Woeginger (Eds.). Lecture Notes in Computer Science, Vol. 1442 . Springer , 13--51. Susanne Albers and Jeffrey Westbrook. 1998. Self-organizing data structures. In Online Algorithms\u2014The State of the Art, Amos Fiat and Gerhard J. Woeginger (Eds.). Lecture Notes in Computer Science, Vol. 1442. Springer, 13--51."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(05)80360-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0461-2"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"117","author":"Angelopoulos Spyros","year":"2018","unstructured":"Spyros Angelopoulos , Christoph D\u00fcrr , and Shendan Jin . 2018 . Online maximum matching with recourse . In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918) (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 117 . Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik GmbH, 8:1\u20138:15. Spyros Angelopoulos, Christoph D\u00fcrr, and Shendan Jin. 2018. Online maximum matching with recourse. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 117. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik GmbH, 8:1\u20138:15."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00638-w"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_2"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997)","author":"Bachrach Ran","year":"1997","unstructured":"Ran Bachrach and Ran El-Yaniv . 1997 . Online list accessing algorithms and their applications: Recent empirical evidence . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997) . Society for Industrial and Applied Mathematics, 53--62. Ran Bachrach and Ran El-Yaniv. 1997. Online list accessing algorithms and their applications: Recent empirical evidence. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997). Society for Industrial and Applied Mathematics, 53--62."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0069-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90209-E"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.238001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_11"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294264"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341.3349"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.03.001"},{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","key":"e_1_2_1_20_1","unstructured":"Allan Borodin and Ran El-Yaniv . 1998. Online Computation and Competitive Analysis . Cambridge University Press . Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1021"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-010-0123-6"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201916) (Leibniz International Proceedings in Informatics LIPIcs)","volume":"53","author":"Boyar Joan","unstructured":"Joan Boyar , Stephan J. Eidenbenz , Lene M. Favrholdt , Michal Kotrb\u010d\u00edk , and Kim S . Larsen.2016. Online dominating set . In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201916) (Leibniz International Proceedings in Informatics LIPIcs) , Vol. 53 . Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik GmbH, 21:1\u201321:15. Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrb\u010d\u00edk, and Kim S. Larsen.2016. Online dominating set. In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201916) (Leibniz International Proceedings in Informatics LIPIcs), Vol. 53. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik GmbH, 21:1\u201321:15."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-017-0536-y"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.03.019"},{"key":"e_1_2_1_26_1","volume-title":"Favrholdt","author":"Boyar Joan","year":"2007","unstructured":"Joan Boyar and Lene M . Favrholdt . 2007 . The relative worst order ratio for on-line algorithms. ACM T. Algor . 3, 2 (2007), article 22, 24 pages. Joan Boyar and Lene M. Favrholdt. 2007. The relative worst order ratio for on-line algorithms. ACM T. Algor. 3, 2 (2007), article 22, 24 pages."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118226.3118464"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-010-0199-4"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 15th International Algorithms and Data Structures Symposium (WADS\u201917)","volume":"10389","author":"Boyar Joan","unstructured":"Joan Boyar , Lene M. Favrholdt , Michal Kotrb\u010d\u00edk , and Kim S . Larsen.2017a. Relaxing the irrevocability requirement for online graph algorithms . In Proceedings of the 15th International Algorithms and Data Structures Symposium (WADS\u201917) (Lecture Notes in Computer Science) , Vol. 10389 . Springer, 217--228. Joan Boyar, Lene M. Favrholdt, Michal Kotrb\u010d\u00edk, and Kim S. Larsen.2017a. Relaxing the irrevocability requirement for online graph algorithms. In Proceedings of the 15th International Algorithms and Data Structures Symposium (WADS\u201917) (Lecture Notes in Computer Science), Vol. 10389. Springer, 217--228."},{"key":"e_1_2_1_30_1","volume-title":"Mikkelsen","author":"Boyar Joan","year":"2017","unstructured":"Joan Boyar , Lene M. Favrholdt , Christian Kudahl , Kim S. Larsen , and Jesper W . Mikkelsen . 2017 b. Online algorithms with advice: A survey. ACM Comput. Surv . 50, 2 (2017), 19:1\u201319:34. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. 2017b. Online algorithms with advice: A survey. ACM Comput. Surv. 50, 2 (2017), 19:1\u201319:34."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.001"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201912)","volume":"7357","author":"Boyar Joan","unstructured":"Joan Boyar , Sushmita Gupta , and Kim S. Larsen . 2012. Access graphs results for LRU versus FIFO under relative worst order analysis . In Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201912) (Lecture Notes in Computer Science) , Vol. 7357 . Springer, 328--339. Joan Boyar, Sushmita Gupta, and Kim S. Larsen. 2012. Access graphs results for LRU versus FIFO under relative worst order analysis. In Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201912) (Lecture Notes in Computer Science), Vol. 7357. Springer, 328--339."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.11.035"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9884-6"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.02.025"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009286"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.07.022"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054115500239"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361786"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-003-0124-9"},{"key":"e_1_2_1_41_1","volume-title":"The relative worst order ratio applied to seat reservation. ACM T. Algor. 4, 4","author":"Boyar Joan","year":"2008","unstructured":"Joan Boyar and Paul Medvedev . 2008. The relative worst order ratio applied to seat reservation. ACM T. Algor. 4, 4 ( 2008 ), article 48, 22 pages. Joan Boyar and Paul Medvedev. 2008. The relative worst order ratio applied to seat reservation. ACM T. Algor. 4, 4 (2008), article 48, 22 pages."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.80"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.06.029"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404017"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009255"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1410890.1410986"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9566-4"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/363095.363141"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1980.230464"},{"volume-title":"Proceedings of the 10th ACM Conference on Electronic Commerce (EC\u201909)","author":"Nikhil","key":"e_1_2_1_50_1","unstructured":"Nikhil R. Devanur and Thomas P. Hayes. 2009. The adwords problem: Online keyword matching with budgeted bidders under random permutations . In Proceedings of the 10th ACM Conference on Electronic Commerce (EC\u201909) . ACM, 71--78. Nikhil R. Devanur and Thomas P. Hayes. 2009. The adwords problem: Online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM Conference on Electronic Commerce (EC\u201909). ACM, 71--78."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2009012"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9800-5"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.04.023"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.015"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9637-3"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/274440.274442"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-9005-9"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-009-0129-5"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/100801901"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"20","author":"Epstein Leah","year":"2013","unstructured":"Leah Epstein , Asaf Levin , Danny Segev , and Oren Weimann . 2013 . Improved bounds for online preemptive matching . In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913) (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 20 . Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik GmbH, 389--399. Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann. 2013. Improved bounds for online preemptive matching. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 20. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik GmbH, 389--399."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0992-3"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49529-2_35"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0821"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_57"},{"key":"e_1_2_1_66_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Goel Gagan","year":"2008","unstructured":"Gagan Goel and Aranyak Mehta . 2008 . Online budgeted matching in random input models with applications to adwords . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908) . Society for Industrial and Applied Mathematics, 982--991. Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to adwords. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). Society for Industrial and Applied Mathematics, 982--991."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/140955276"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.34"},{"key":"e_1_2_1_70_1","volume-title":"C","author":"Gy\u00e1rf\u00e1s Andr\u00e1s","year":"1990","unstructured":"Andr\u00e1s Gy\u00e1rf\u00e1s and Jen\u0151 Lehel . 1990. First fit and on-line chromatic number of families of graphs. Ars Comb. 29 , C ( 1990 ), 168--176. Andr\u00e1s Gy\u00e1rf\u00e1s and Jen\u0151 Lehel. 1990. First fit and on-line chromatic number of families of graphs. Ars Comb. 29, C (1990), 168--176."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.017"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.09.013"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.021"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_44"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15155-2_3"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90086-W"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_26"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80026-7"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203025"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762111"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268042"},{"key":"e_1_2_1_85_1","volume-title":"Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201996)","author":"Kenyon Claire","year":"1996","unstructured":"Claire Kenyon . 1996 . Best-fit bin-packing with random order . In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201996) . Society for Industrial and Applied Mathematics, 359--364. Claire Kenyon. 1996. Best-fit bin-packing with random order. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201996). Society for Industrial and Applied Mathematics, 359--364."},{"key":"e_1_2_1_86_1","volume-title":"Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"58","author":"Komm Dennis","year":"2016","unstructured":"Dennis Komm , Rastislav Kr\u00e1lovi\u010d , Richard Kr\u00e1lovi\u010d , and Christian Kudahl . 2016 . Advice complexity of the online induced subgraph problem . In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 58 . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 59:1\u201359:13. Dennis Komm, Rastislav Kr\u00e1lovi\u010d, Richard Kr\u00e1lovi\u010d, and Christian Kudahl. 2016. Advice complexity of the online induced subgraph problem. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 58. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 59:1\u201359:13."},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796299540"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.05.022"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.13.4.609"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1137\/130917703"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875567"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.132"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170081"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-007-0019-7"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132587"},{"volume-title":"On-Line Algorithms","author":"Raghavan Prabhakar","key":"e_1_2_1_96_1","unstructured":"Prabhakar Raghavan . 1992. A statistical adversary for on-line algorithms . In On-Line Algorithms ( DIMACS : Series in Discrete Mathematics and Theoretical Computer Science), Vol. 7 . American Mathematical Society , 79--83. Prabhakar Raghavan. 1992. A statistical adversary for on-line algorithms. In On-Line Algorithms (DIMACS: Series in Discrete Mathematics and Theoretical Computer Science), Vol. 7. American Mathematical Society, 79--83."},{"key":"e_1_2_1_97_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"57","author":"Rawitz Dror","year":"2016","unstructured":"Dror Rawitz and Adi Ros\u00e9n . 2016 . Online budgeted maximum coverage . In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 57 . Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik GmbH, 73:1\u201373:17. Dror Rawitz and Adi Ros\u00e9n. 2016. Online budgeted maximum coverage. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 57. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik GmbH, 73:1\u201373:17."},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.60"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90150-8"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1099"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3425910","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3425910","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:24Z","timestamp":1750195464000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3425910"}},"subtitle":["A Survey"],"short-title":[],"issued":{"date-parts":[[2021,1,2]]},"references-count":102,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3425910"],"URL":"https:\/\/doi.org\/10.1145\/3425910","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"type":"print","value":"0360-0300"},{"type":"electronic","value":"1557-7341"}],"subject":[],"published":{"date-parts":[[2021,1,2]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}