TY - GEN
T1 - Approximating permanents of complex matrices
AU - Fürer, Martin
PY - 2000
Y1 - 2000
N2 - A wide variety of approximation algorithms for permanents of non-negative matrices has been proposed and analyzed before [5; 7; 9; 1]. Usually, these approximation algorithms have been presented for 0-1 matrices and it has been remarked that they extend to other matrices as long as all entries are non-negative. Here we present the first approximation algorithm for the permanent of an arbitrary complex matrix. We extend the notion of an (ε,δ)-approximation algorithm to accommodate for cancellations in additions. Our running time is Õ(3n/2 ε-2 log 1/δ) compared to Õ(2n/2 ε-2 log 1/δ) for non-negative matrices. (A faster algorithm is known for 0-1 matrices [6].).
AB - A wide variety of approximation algorithms for permanents of non-negative matrices has been proposed and analyzed before [5; 7; 9; 1]. Usually, these approximation algorithms have been presented for 0-1 matrices and it has been remarked that they extend to other matrices as long as all entries are non-negative. Here we present the first approximation algorithm for the permanent of an arbitrary complex matrix. We extend the notion of an (ε,δ)-approximation algorithm to accommodate for cancellations in additions. Our running time is Õ(3n/2 ε-2 log 1/δ) compared to Õ(2n/2 ε-2 log 1/δ) for non-negative matrices. (A faster algorithm is known for 0-1 matrices [6].).
UR - http://www.scopus.com/inward/record.url?scp=0033717560&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0033717560&partnerID=8YFLogxK
U2 - 10.1145/335305.335399
DO - 10.1145/335305.335399
M3 - Conference contribution
AN - SCOPUS:0033717560
SN - 1581131844
SN - 9781581131840
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 667
EP - 669
BT - Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
T2 - 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Y2 - 21 May 2000 through 23 May 2000
ER -