# On the power of randomization in on-line algorithms

@article{BenDavid2005OnTP, title={On the power of randomization in on-line algorithms}, author={Shai Ben-David and Allan Borodin and Richard M. Karp and G{\'a}bor Tardos and Avi Wigderson}, journal={Algorithmica}, year={2005}, volume={11}, pages={2-14} }

Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient “simulation” of randomized on-line algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases.

#### Topics from this paper

#### 189 Citations

Randomized distributed online algorithms against adaptive offline adversaries

- Computer Science
- Inf. Process. Lett.
- 2020

It is proved that in a distributed setting, this result does not necessarily hold, so randomization against an adaptive, offline adversary becomes interesting again. Expand

On the Power of Randomization in Distributed Algorithms in Dynamic Networks with Adaptive Adversaries

- Computer Science
- Euro-Par
- 2020

It is proved that randomness offers limited power to better deal with “bad” adaptive adversary, and that P can always be converted to a new algorithm Q with comparable time complexity, even when Q runs against prophetic adversaries. Expand

Derandomizing Online Algorithms

- 2014

The aim of this work is to find methods for reducing the amount of randomness needed for implementing online algorithms, without hurting their efficiency. We call an online algorithm… Expand

A 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines

- Mathematics, Computer Science
- 2009

This work claims that the phi-competitive deterministic online algorithm by Li et al. can be slightly simplified, while retaining its competitive ratio, and argues that the competitive ratio against oblivious adversary is at most 4/3. Expand

A Universal Randomized Packet Scheduling Algorithm

- Computer Science
- Algorithmica
- 2012

ReMix is the optimal memoryless randomized algorithm against adaptive adversary for Packet Scheduling, and its general analysis yields improved performance guarantees for several restricted variants, including the s-bounded instances. Expand

The weighted 2-server problem

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2004

It is proved that, in uniform spaces, a version of the work function algorithm is 5-competitive, and that no better ratio is possible, and a matching lower bound is given. Expand

Randomized algorithm for the k-server problem on decomposable spaces

- Computer Science, Mathematics
- J. Discrete Algorithms
- 2009

This method yields o ( k ) -competitive algorithms solving the randomized k-server problem for some special underlying metric spaces, e.g. HSTs of "small" height (but unbounded degree). Expand

Randomized competitive algorithms for online buffer management in the adaptive adversary model

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2011

A new analysis of a previously known algorithm is given, which shows that it remains e / ( e − 1 ) -competitive even against an adaptive adversary, and a 4/3 lower bound on the competitive ratio on 2-bounded instances, in which each packet has a lifespan of one or two steps is given. Expand

Randomized Priority Algorithms: (Extended Abstract)

- Computer Science
- WAOA
- 2003

This work extends the model of Borodin, Nielsen and Rackoff so as to formally define "randomized greedy-like algorithms" and be able to prove lower bounds on the proximability of a certain problem by such a class of algorithms. Expand

Memoryless Algorithms for the Generalized k-server Problem on Uniform Metrics

- Computer Science, Mathematics
- WAOA
- 2020

It is shown that the Harmonic Algorithm achieves this competitive ratio and provides matching lower bounds, which improves the doubly-exponential bound of Chiplunkar and Vishwanathan for the more general setting of uniform metrics with different weights. Expand

#### References

SHOWING 1-10 OF 17 REFERENCES

A strongly competitive randomized paging algorithm

- Computer Science
- Algorithmica
- 2005

The partitioning algorithm is developed, a randomized on-line algorithm for the paging problem, which it is proved that its expected cost on any sequence of requests is within a factor ofHk of optimum. Expand

Memory Versus Randomization in On-line Algorithms (Extended Abstract)

- Computer Science
- ICALP
- 1989

The amortized analysis of LRU shows that it achieves optimal worst-case performance (this will be made precise in section 2). Expand

Infinite games: randomization, computability, and applications to online problems

- Mathematics, Computer Science
- STOC '91
- 1991

It is shown that, whereas all open games are semicompu tably determinate, there is a semicomputab]y indeterminate e closed game, and the proof for the indeterminacy result requires a new diagonalization technique, which might be useful in other similar cases. Expand

Competitive Paging Algorithms

- Computer Science
- J. Algorithms
- 1991

The marking algorithm is developed, a randomized on-line algorithm for the paging problem, which it is proved that its expected cost on any sequence of requests is within a factor of 2Hk of optimum. Expand

A competitive 3-server algorithm

- Computer Science
- SODA '90
- 1990

This work proves that a simple, natural randomized algorithm is competitive for the 3-server problem, where to serve a request is to move one of the k servers to the request site. Expand

Competitive k-Server Algorithms

- Computer Science
- J. Comput. Syst. Sci.
- 1994

Deterministic competitive k-server algorithms are given for all k and all metric spaces and the competitive ratio can be proved is exponential in the number of servers, which settles the k- server conjecture. Expand

The harmonic online K-server algorithm is competitive

- Computer Science, Mathematics
- STOC '91
- 1991

The Harmonic algorithm for the online K-server problem is shown to be competitive against an adaptive online adversary for K 22 and the best competitive ratios that have been published so far for online algorithms over a general metric space when K >2 are shown. Expand

New results on server problems

- Computer Science, Mathematics
- SODA '90
- 1990

A fast algorithm for oflline computing of an optimal schedule is given, and it is shown that finding an optimal offline schedule is at least as hard as the assignment problem. Expand

Competitive algorithms for on-line problems

- Computer Science, Mathematics
- STOC '88
- 1988

This paper presents several general results concerning competitive algorithms, as well as results on specific on-line problems. Expand

The harmonic k-server algorithm is competitive

- Computer Science
- JACM
- 2000

A simple proof that the Harmonic Harmonic k-server algorithm is competitive is given, and the competitive ratio is proved to be the best currently known fo the algorithm. Expand