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