A Monte-Carlo Algorithm for Estimating the Permanent
Title | A Monte-Carlo Algorithm for Estimating the Permanent |
Publication Type | Technical Report |
Year of Publication | 1990 |
Authors | Karmarkar, N., Karp R. M., Lipton R. J., Lovász L., & Luby M. |
Other Numbers | 627 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-063.pdf |
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 |