2026-07-21T23:33:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4480 2024-03-06T10:35:06Z ddc:004 open_access

Randomized Online Algorithms with High Probability Guarantees Komm, Dennis Královic, Rastislav Královic, Richard Mömke, Tobias Online Algorithms Randomization High Probability We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we define a broad class of online problems that includes some of the well-studied problems like paging, k-server and metrical task systems on finite metrics, and show that for these problems it is possible to obtain, given an algorithm with constant expected competitive ratio, another algorithm that achieves the same solution quality up to an arbitrarily small constant error with high probability; the "high probability" statement is in terms of the optimal cost. Furthermore, we show that our assumptions are tight in the sense that removing any of them allows for a counterexample to the theorem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dennis Komm and Rastislav Královic and Richard Královic and Tobias Mömke 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.470 urn:nbn:de:0030-drops-44803 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.470 eng https://creativecommons.org/licenses/by/3.0/legalcode