Randomized Algorithms

Motwani, R., & Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press.

Type

Book

Intellectual base

Review or monograph

Year

1995

DOI

10.1017/cbo9780511814075

ISBN

9780521474658

Link

https://www.cambridge.org/9780521474658

Cited from

computer_science

Cited by

3 citations across 3 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Algorithm
  • The input-to-output deterministic-or-randomized mapping (Motwani & Raghavan, 1995)

    This sourceCanonical reference unifying deterministic and randomized algorithms as input-to-output mappings, distinguishing Las Vegas from Monte Carlo procedures

• Livelock
  • Two further inferences follow. Randomness is a genuine solution, not a hack: in distributed systems and traffic alike, the cleanest break of a symmetric standoff is stochastic divergence, and much of the randomised-algorithm tradition is, at root, about livelock avoidance.

    This sourceRandomization (including backoff and symmetry-breaking) as a principled tool for breaking symmetric standoffs in distributed computation.

Domain-specific

• Isolation lemma
  • The entry states the combinatorial probability lemma and its reasoning role, not an implementation, cryptographic primitive, or guarantee that one trial will succeed.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Links previously used in the corpus

Before the registry existed this work was also linked 1 other way.

• https://doi.org/10.1017/CBO9780511814075 ×1

Registry ID ref:c7e940fb6607 · see in the full table