## An Analysis of a Monte Carlo Algorithm for Estimating the
Permanent

**Mark Jerrum**
*Abstract:* Karmarkar, Karp, Lipton, Lovász, and
Luby proposed a Monte Carlo algorithm for approximating the
permanent of a non-negative *n* x *n* matrix, which is
based on an easily computed, unbiased estimator. It is not
difficult to construct 0,1-matrices for which the variance of this
estimator is very large, so that an exponential number of trials
are necessary to obtain a reliable approximation that is within a
constant factor of the correct value. Nevertheless, the same
authors conjectured that for almost every 0,1-matrix the variance
of the estimator is small. The conjecture is shown to be true;
indeed for almost every 0,1 matrix, O(*nw(n)e^{-2}*) trials
suffice to obtain a reliable approximation that is within a factor
(1 + e) of the correct value. Here *w(n)* is any function
tending to infinity as *n* tends to infinity.

*LFCS report ECS-LFCS-91-164*

Previous |

Index |

Next