𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Assessing the Performance of Randomized Algorithms

✍ Scribed by Sorana Froda

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
145 KB
Volume
37
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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 randomness of the input, which needs to be modeled. We illustrate our idea on two classes of problems: primality testing and fingerprinting in strings transmission. Although in both cases the randomization has low error, in the first one the probability of a false positive is very low, while in the second one it is not. We end the paper with a discussion of randomness illustrated in a textbook example.

πŸ“œ SIMILAR VOLUMES

On the performance of peeling algorithms
On the performance of peeling algorithms
✍ Petitjean, Michel ;Saporta, Gilbert πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 453 KB

## Abstract The peeling of a __d__‐dimensional set of points is usually performed with successive calls to a convex hull algorithm; the optimal worst‐case convex hull algorithm, known to have an __O__(__n__^Λ™^ Log (n)) execution time, may give an __O__(__n__^Λ™^__n__^Λ™^ Log (n)) to peel all the set;

Assessing the performance of matching al
Assessing the performance of matching algorithms when selection into treatment is strong
✍ Boris Augurzky; Jochen Kluve πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 190 KB

## Abstract This paper investigates the method of matching regarding two crucial implementation choices: the distance measure and the type of algorithm. We implement optimal full matchingβ€”a fully efficient algorithmβ€”and present a framework for statistical inference. The implementation uses data fro

The effect of multipath interference on
The effect of multipath interference on the performance of random accessing
✍ Jyh-Horng Wen; Jin-Fu Chang πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 321 KB πŸ‘ 2 views

This paper studies the effect of multipath interference on the performance of random access techniques in which the power level of a packet depends on its time of arrival. The protocols considered are pure ALOHA and slotted ALOHA. Key performance measures such as channel throughout and mean packet d