TY - JOUR
T1 - An almost linear time approximation algorithm for the permanent of a random (0-1) matrix
AU - Fürer, Martin
AU - Kasiviswanathan, Shiva Prasad
N1 - Funding Information:
★ Research supported in part by NSF Grant CCR-0209099.
PY - 2004
Y1 - 2004
N2 - We present a simple randomized algorithm for approximating permanents. The algorithm with inputs A, ∈ > 0 produces an output XA with (1 - ∈)per(A) ≤ XA ≤ (1 + ∈)per(A) for almost all (0-1) matrices A. For any positive constant ∈ > 0, and almost all (0-1) matrices the algorithm runs in time O(n2ω), i.e., almost linear in the size of the matrix, where ω = ω(n) is any function satisfying ω(n) → ∞ as n → ∞. This improves the previous bound of O(n3ω) for such matrices. The estimator can also be used to estimate the size of a backtrack tree.
AB - We present a simple randomized algorithm for approximating permanents. The algorithm with inputs A, ∈ > 0 produces an output XA with (1 - ∈)per(A) ≤ XA ≤ (1 + ∈)per(A) for almost all (0-1) matrices A. For any positive constant ∈ > 0, and almost all (0-1) matrices the algorithm runs in time O(n2ω), i.e., almost linear in the size of the matrix, where ω = ω(n) is any function satisfying ω(n) → ∞ as n → ∞. This improves the previous bound of O(n3ω) for such matrices. The estimator can also be used to estimate the size of a backtrack tree.
UR - http://www.scopus.com/inward/record.url?scp=32144448996&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=32144448996&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-30538-5_22
DO - 10.1007/978-3-540-30538-5_22
M3 - Article
AN - SCOPUS:32144448996
SN - 0302-9743
VL - 3328
SP - 263
EP - 274
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -