AN ANALYSIS OF A MONTE-CARLO ALGORITHM FOR ESTIMATING THE PERMANENT

Karmarkar, Karp, Lipton, Lovasz;, 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 is necessary to obtain a reliable approximation that is within a constant factor of the correct value. Nevertheless, the same authors conjectured that for a random 0,1-matrix the variance of the estimator is typically small. The conjecture is shown to be true; indeed, for almost every 0,1-matrix A, just O(nw(n)epsilon(-2)) trials suffice to obtain a reliable approximation to the permanent of A within a factor Ifs of the correct value. Here w(n) is any function tending to infinity as n --> infinity. This result extends to random 0,1-matrices with density at least n(-1/2)w(n). It is also shown that polynomially many trials suffice to approximate the permanent of any dense O,l-matrix, i.e., one in which every row- and column-sum is at least (1/2 + alpha)n, for some constant alpha > 0. The degree of the polynomial bounding the number of trials Is a function of alpha, and increases as alpha --> infinity.