ABSTRACT

Randomization (i.e., the use of random choice as an algorithmic step) is one of the most interesting tools in designing efficient algorithms. A remarkable property of randomized algorithms is their structural simplicity. In fact, in several cases, although the known deterministic algorithms are quite involved, the randomized ones are simpler and much easier to code.