Article ID: | iaor19921405 |
Country: | Netherlands |
Volume: | 34 |
Start Page Number: | 165 |
End Page Number: | 201 |
Publication Date: | Nov 1991 |
Journal: | Discrete Applied Mathematics |
Authors: | Karp Richard M. |
Keywords: | adaptive processes |
Research conducted over the past fifteen years has amply demonstrated the advantages of algorithms that make random choices in the course of their execution. This paper presents a wide variety of examples intended to illustrate the range of applications of randomized algorithms, and the general principles and approaches that are of greatest use in their construction. The examples are drawn from many areas, including number theory, algebra, graph theory, pattern matching, selection, sorting, searching, computational geometry, combinatorial enumeration, and parallel and distributed computation.