Academic
Publications
Randomized Algorithms

Randomized Algorithms,10.1145/211542.606546,Rajeev Motwani,Prabhakax Raghavan

Randomized Algorithms   (Citations: 2635)
BibTex | RIS | RefWorks Download
The last decade has witnessed a tremendous growth in the area of randomized algorithms.During this period, randomized algorithms went from being a tool in computational number theory to finding widespread application in many types of algorithms. Two benefits of randomization have spearheaded this growth: simplicity and speed. For many applications, a randomized algorithm is the simplest algorithm available, or the fastest, or both. This book presents the basic concepts in the design and analysis of randomized algorithms at a level accessible to advanced undergraduates and to graduate students. We expect it will also prove to be a reference to professionals wishing to implement such algorithms and to researchers seeking to establish new results in the area.
Published in 1995.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...There are two key techniques which make randomness a practical tool in the design of centralised algorithms, both familiar from textbooks on randomised algorithms [102, 104]...
    • ...In this case, we can resort to a very simple algorithm, familiar from introductory courses to randomised algorithms: ip a fair coin for each node to determine its side [98, 102, 104]...
    • ...SAT) problem: choose a random assignment [102, 104]...

    Jukka Suomela. Survey of local algorithms

    • ...The use of randomized algorithms [44] is hence necessary to address this type of problems...
    • ...To analyze the effectiveness of a randomized algorithm, it is important to study the probability distribution of its output or various performance metrics [44]...

    Andrea Arcuriet al. A practical guide for using statistical tests to assess randomized alg...

    • ...They usually make use of the Zipf distribution (or generally, Zipf-like distribution) [1], which models a large number of natural skewed distributions well [20]...
    • ...Therefore, some researchers [13,20,57] bring data skew into theoretical analyses of their algorithms...
    • ...Cormode and Muthukrishnan [20] analyzed the space requirements for the Count-Min sketch to deal with point queries and top-k queries...

    Hongyan Liuet al. Methods for mining frequent items in data streams: an overview

    • ...knownasMarkov’sinequality[19].Let X bearandomvariableassumingnon-negative values with expectation E[X]...

    Petros Drineaset al. Faster least squares approximation

    • ...Furthermore, since the product of the determinants is a nonzero polynomial, if we choose the mixing coefficients uniformly and independently from a large enough field F, then the probability that the product evaluates to a nonzero value can be made arbitrarily close to 1; this can be established via the Schwartz–Zippel Theorem (e.g., [9], according to Ho et al. [3])...

    Baochun Liet al. Network Coding

Sort by: