Publication Details
Title: A Monte-Carlo Algorithm for Estimating the Permanent
Author: N. Karmarkar, R. Karp, R. Lipton, L. Lovasz, and M. Luby
Group: ICSI Technical Reports
Date: November 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-063.pdf
Overview:
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$.
Author: N. Karmarkar, R. Karp, R. Lipton, L. Lovasz, and M. Luby
Group: ICSI Technical Reports
Date: November 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-063.pdf
Overview:
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 Information:
ICSI Technical Report TR-90-063
Bibliographic Reference:
N. Karmarkar, R. Karp, R. Lipton, L. Lovasz, and M. Luby. A Monte-Carlo Algorithm for Estimating the Permanent. ICSI Technical Report TR-90-063, November 1990