Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Computational Number Theory
Graduate Student
Randomized Algorithm
Related Publications
(182)
The Probabilistic Method
Parallel algorithms and architectures
Expected time bounds for selection
Algorithms for random generation and counting  a Markov chain approach
Probabilistic computation: towards a unified measure of complexity
Subscribe
Academic
Publications
Randomized Algorithms
Randomized Algorithms,10.1145/211542.606546,Rajeev Motwani,Prabhakax Raghavan
Edit
Randomized Algorithms
(
Citations: 2635
)
BibTex

RIS

RefWorks
Download
Rajeev Motwani
,
Prabhakax Raghavan
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.
DOI:
10.1145/211542.606546
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.
(
portal.acm.org
)
(
doi.acm.org
)
(
www.informatik.unitrier.de
)
(
portal.acm.org
)
(
portal.acm.org
)
More »
Citation Context
(1508)
...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 Arcuri
,
et al.
A practical guide for using statistical tests to assess randomized alg...
...They usually make use of the Zipf distribution (or generally, Zipflike 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 CountMin sketch to deal with point queries and topk queries...
Hongyan Liu
,
et al.
Methods for mining frequent items in data streams: an overview
...knownasMarkov’sinequality[
19
].Let X bearandomvariableassumingnonnegative values with expectation E[X]...
Petros Drineas
,
et 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 Li
,
et al.
Network Coding
Sort by:
Citations
(2635)
Survey of local algorithms
(
Citations: 14
)
Jukka Suomela
Published in 2012.
Don’t Lose Sleep Over Availability: The GreenUp Decentralized Wakeup Service
Siddhartha Sen
,
Jacob R. Lorch
,
Richard Hughes
,
Carlos Garcia Jurado Suarez
,
Brian Zill
,
Weverton Cordeiro
,
Jitendra Padhye
Published in 2012.
GreenUp: A Decentralized System for Making Sleeping Machines Available
Siddhartha Sen
,
Jacob R. Lorch
,
Richard Hughes
,
Carlos Garcia
,
Brian Zill
,
Weverton Cordeiro
,
Jitendra Padhye
Published in 2012.
Linking Operational Semantics and Algebraic Semantics for a Probabilistic Timed Sharedvariable Language
Huibiao Zhu
,
Fan Yang
,
Jifeng He
,
Jonathan P. Bowen
,
Jeff W. Sanders
,
Shengchao Qin
Journal:
The Journal of Logic and Algebraic Programming  JLP
, vol. 81, no. 1, 2012
A Martingale Representation for Matching Estimators
Alberto Abadie
,
Guido W. Imbens
Journal:
Journal of The American Statistical Association  J AMER STATIST ASSN
, vol. justaccep, no. justaccep, 2012