๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the power of randomization in on-line algorithms

โœ Scribed by S. Ben-David; A. Borodin; R. Karp; G. Tardos; A. Wigderson

Publisher
Springer
Year
1994
Tongue
English
Weight
797 KB
Volume
11
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

More on randomized on-line algorithms fo
More on randomized on-line algorithms for caching
โœ Marek Chrobak; Elias Koutsoupias; John Noga ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 143 KB

We address the tradeo between the competitive ratio and the resources used by randomized on-line algorithms for caching. Two algorithms reported in the literature that achieve the optimal ratio H k require a lot of memory and perform extensive computation at each step. On the other hand, a very simp

On Assessing the Performance of Randomiz
On Assessing the Performance of Randomized Algorithms
โœ Sorana Froda ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 145 KB

In this paper we study randomized algorithms with random input. We adapt to such algorithms the notion of probability of a false positive which is common in epidemiological studies. The probability of a false positive takes into account both the (controlled) error of the randomization and the random

On limits on the computational power of
On limits on the computational power of data-accumulating algorithms
โœ Stefan D Bruda; Selim G Akl ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 102 KB

In the data-accumulating paradigm, inputs arrive continuously in real time, and the computation terminates when all the already received data are processed before another datum arrives. Previous research states that a constant upper bound on the running time of a successful algorithm within this par