A Monte-Carlo Algorithm for Estimating the Permanent

TitleA Monte-Carlo Algorithm for Estimating the Permanent
Publication TypeTechnical Report
Year of Publication1990
AuthorsKarmarkar, N., Karp R. M., Lipton R. J., Lovász L., & Luby M.
Other Numbers627

Let $A$ be an $n imes n$ matrix with 0-1 valued entries, and let $PER(A)$ be the permanent of $A$. We describe a Monte-Carlo algorithm which produces a ``good in the relative sense'' estimate of $PER(A)$ and has running time $POLY(n) 2^{n/2}$, where $POLY(n)$ denotes a function that grows polynomially with $n$. Key Words: permanent, matching, Monte-Carlo algorithm, algorithm, bipartite graph, determinant.

Bibliographic Notes

ICSI Technical Report TR-90-063

Abbreviated Authors

N. Karmarkar, R. Karp, R. Lipton, L. Lovasz, and M. Luby

ICSI Publication Type

Technical Report