Randomized Online Algorithms with High Probability Guarantees
From MaRDI portal
Abstract: We study the relationship between the competitive ratio and the tail distribution of randomized online minimization 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 a 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. In addition, there are examples of other problems not covered by our definition, where similar high probability results can be obtained.
Recommendations
- Randomized online computation with high probability guarantees
- On the power of randomization in on-line algorithms
- On-Line Probability, Complexity and Randomness
- Entropy-based bounds for online algorithms
- Randomized approximation and online algorithms for assignment problems
- Randomized algorithms for online knapsack problems
- Stochastic dominance and the bijective ratio of online algorithms
- Randomized algorithms for online bounded bidding
- A technique to obtain hardness results for randomized online algorithms -- a survey
Cited in
(2)
This page was built for publication: Randomized Online Algorithms with High Probability Guarantees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2965509)
