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 |