Randomized Online Computation with High Probability Guarantees
Open Access
- 30 January 2022
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1357-1384
Abstract
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 r implies the existence of a randomized online algorithm that has a competitive ratio of $$(1+\varepsilon )r$$ with high probability, 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, k-server, and metrical task systems on finite metric spaces.
Keywords
Funding Information
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (200021–146372)
- Deutsche Forschungsgemeinschaft (BL511/10-1, MO 2889/1-1)
This publication has 11 references indexed in Scilit:
- An Introduction to Online Computation2016
- The -server problemComputer Science Review, 2009
- On-line Randomized Call Control RevisitedSIAM Journal on Computing, 2001
- Competitive analysis of randomized paging algorithmsTheoretical Computer Science, 2000
- An optimal on-line algorithm for metrical task systemJournal of the ACM, 1992
- Competitive paging algorithmsJournal of Algorithms, 1991
- Competitive algorithms for server problemsJournal of Algorithms, 1990
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- Weighted sums of certain dependent random variablesTohoku Mathematical Journal, 1967
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963