Home / research areas / RA
Randomized Algorithms
A randomized algorithm is a non-deterministic algorithm whose control flow is determined during its execution. Each choice is drawn according to a given known probability distribution, and therefore running time, performance, and possibly even the correctness are considered as random variables. Although randomness leads to non-determinism, that is undesired in some situations, in many other cases the more powerful computation model can improve considerably the running time or the quality of a solution. This is the case of applications in combinatorial optimization, machine learning, communication networks, and security protocols. Probabilistic techniques have a prominent role in the algorithm theory. For example, beyond determining an algorithm’s control flow, probability distributions can also be used to describe the algorithm input instance. This allows modeling instances for real life problems, and yet obtain a formal analysis and understanding that conform to empirical results. Another closely related example is the study of stochastic problems, when the input instance itself consists of probability distributions. For some problems, randomness is not necessary to obtain good and fast solutions. Nevertheless, understanding randomized algorithms is a valuable tool to obtain algorithms that would not be arisen naturally in a purely deterministic approach, or that would be hard to analyze without probability theory. Indeed, in some cases it is possible to apply standard derandomization techniques to obtain deterministic algorithms.
Problems:
- minimum cut;
- maximum satisfiability problem;
- facility location problems;
- k-server;
- independent set;
- combinatorial auction;
- searching and sorting;
- pattern recognition.
References:
- Michael Mitzenmacher e Eli Upfal. Probability and Computing - Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. Amazon
- Rajeev Motwani e Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Amazon