An introduction to randomized algorithms

DOI10.1016/0166-218X(91)90086-CzbMath0757.68085OpenAlexW2160365721MaRDI QIDQ1182319

Richard M. Karp

Publication date: 28 June 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(91)90086-c

zbMATH Keywords

randomizationMonte Carlo algorithmfingerprintingLas Vegas algorithm

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Exact enumeration problems, generating functions (05A15) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Number-theoretic algorithms; complexity (11Y16) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel numerical computation (65Y05)

Related Items

Estimation of singular values of very large matrices using random sampling, A PARALLEL ALGORITHM FOR FIXED-DIMENSIONAL LINEAR PROGRAMMING∗, A stochastic algorithm for online bipartite resource allocation problems, Model Checking Temporal Properties of Recursive Probabilistic Programs, A comprehensive review of quantum random number generators: concepts, classification and the origin of randomness, Lower space bounds for randomized computation, Monte Carlo and Las Vegas randomized algorithms for systems and control. An introduction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• The choice coordination problem
• Small-dimensional linear programming and convex hulls made easy
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• A fast Las Vegas algorithm for triangulating a simple polygon
• Randomized search trees
• TWO THEOREMS IN GRAPH THEORY
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Self-adjusting binary search trees
• Efficient randomized pattern-matching algorithms
• Sorting in Average Time $o(\log \,n)$
• The Knowledge Complexity of Interactive Proof Systems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• A Monte-Carlo Algorithm for Estimating the Permanent
• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• IP = PSPACE
• An optimal algorithm for intersecting line segments in the plane
• Paths, Trees, and Flowers
• Factoring Polynomials Over Large Finite Fields
• The Factorization of Linear Graphs