A Monte-Carlo Algorithm for Estimating the Permanent
- 1 April 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 22 (2) , 284-293
- https://doi.org/10.1137/0222021
Abstract
Let A be an n \Theta n matrix with 0-1 valued entries, and let per(A) be the permanentof A. We describe a Monte-Carlo algorithm which produces a "goodin the relative sense" estimate of per(A) and has running time poly(n)2n=2,where poly(n) denotes a function that grows polynomially with n.1 IntroductionLet A be an n \Theta n matrix with 0-1 valued entries, let det(A) denote the determinantof A and let per(A) denote the permanent of A. The marked contrast between thecomputational...Keywords
This publication has 10 references indexed in Scilit:
- Approximating the PermanentSIAM Journal on Computing, 1989
- Monte-Carlo approximation algorithms for enumeration problemsJournal of Algorithms, 1989
- On the power of two-point based samplingJournal of Complexity, 1989
- RSA and Rabin Functions: Certain Parts are as Hard as the WholeSIAM Journal on Computing, 1988
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986
- Random generation of combinatorial structures from a uniform distributionTheoretical Computer Science, 1986
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Combinatorial MathematicsPublished by American Mathematical Society (AMS) ,1963
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952