{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:00Z","timestamp":1740109320693,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,1,30]],"date-time":"2022-01-30T00:00:00Z","timestamp":1643500800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,30]],"date-time":"2022-01-30T00:00:00Z","timestamp":1643500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"schweizerischer nationalfonds zur f\u00f6rderung der wissenschaftlichen forschung","doi-asserted-by":"publisher","award":["200021\u2013146372"],"award-info":[{"award-number":["200021\u2013146372"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"deutsche forschungsgemeinschaft","doi-asserted-by":"publisher","award":["BL511\/10-1","MO 2889\/1-1"],"award-info":[{"award-number":["BL511\/10-1","MO 2889\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected competitive ratio <jats:italic>r<\/jats:italic> implies the existence of a randomized online algorithm that has a competitive ratio of <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1+\\varepsilon )r$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mi>r<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula><jats:italic>with high probability<\/jats:italic>, measured with respect to the optimal profit or cost, respectively. The class of problems includes some of the well-studied online problems such as paging, <jats:italic>k<\/jats:italic>-server, and metrical task systems on finite metric spaces.<\/jats:p>","DOI":"10.1007\/s00453-022-00925-z","type":"journal-article","created":{"date-parts":[[2022,1,30]],"date-time":"2022-01-30T03:02:15Z","timestamp":1643511735000},"page":"1357-1384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Randomized Online Computation with High Probability Guarantees"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9024-1558","authenticated-orcid":false,"given":"Dennis","family":"Komm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rastislav","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,30]]},"reference":[{"issue":"3","key":"925_CR1","doi-asserted-by":"publisher","first-page":"357","DOI":"10.2748\/tmj\/1178243286","volume":"19","author":"K Azuma","year":"1967","unstructured":"Azuma, K.: Weighted sums of certain dependent random variables. T\u00f4hoku Math. J. 19(3), 357\u2013367 (1967)","journal-title":"T\u00f4hoku Math. J."},{"issue":"1\u20132","key":"925_CR2","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0304-3975(98)00116-9","volume":"234","author":"D Achlioptas","year":"2000","unstructured":"Achlioptas, D., Chrobak, M., Noga, J.: Competitive analysis of randomized paging algorithms. Theoret. Comput. Sci. 234(1\u20132), 203\u2013218 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"925_CR3","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"4","key":"925_CR4","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A Borodin","year":"1992","unstructured":"Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. J. ACM 39(4), 745\u2013763 (1992)","journal-title":"J. ACM"},{"issue":"4","key":"925_CR5","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A Fiat","year":"1991","unstructured":"Fiat, A., Karp, R.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E.: Competitive paging algorithms. J. Algorithms 12(4), 685\u2013699 (1991)","journal-title":"J. Algorithms"},{"issue":"301","key":"925_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"925_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-27903-2","volume-title":"Design and Analysis of Randomized Algorithms","author":"J Hromkovi\u010d","year":"2005","unstructured":"Hromkovi\u010d, J.: Design and Analysis of Randomized Algorithms. Springer, Berlin (2005)"},{"unstructured":"Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: Randomized online algorithms with high probability guarantees. In: Proceedings\u00a0of STACS 2014, LIPIcs, vol.\u00a025, pp.\u00a0470\u2013481 (2014)","key":"925_CR8"},{"key":"925_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42749-2","volume-title":"An Introduction to Online Computation: Determinism, Randomization, Advice","author":"D Komm","year":"2016","unstructured":"Komm, D.: An Introduction to Online Computation: Determinism, Randomization, Advice. Springer, Berlin (2016)"},{"issue":"2","key":"925_CR10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.cosrev.2009.04.002","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E.: The $$k$$-server problem. Comput. Sci. Rev. 3(2), 105\u2013118 (2009)","journal-title":"Comput. Sci. Rev."},{"issue":"1","key":"925_CR11","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/S0097539798346706","volume":"31","author":"S Leonardi","year":"2001","unstructured":"Leonardi, S., Marchetti-Spaccamela, A., Presciutti, A., Ros\u00e9n, A.: On-line randomized call control revisited. SIAM J. Comput. 31(1), 86\u2013112 (2001)","journal-title":"SIAM J. Comput."},{"unstructured":"Maggs, B.M., Meyer auf der Heide, F., Voecking, B., Westermann, M.: Exploiting locality for networks of limited bandwidth. In: Proceedings\u00a0of FOCS\u00a01997, pp.\u00a0284\u2013293 (1997)","key":"925_CR12"},{"issue":"2","key":"925_CR13","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"MS Manasse","year":"1990","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for on-line problems. J. Algorithms 11(2), 208\u2013230 (1990)","journal-title":"J. Algorithms"},{"issue":"2","key":"925_CR14","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00925-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00925-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00925-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T05:03:43Z","timestamp":1651122223000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00925-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,30]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["925"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00925-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,30]]},"assertion":[{"value":"16 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}