Computing the Permanent of (Some) Complex Matrices |
| |
Authors: | Alexander Barvinok |
| |
Institution: | 1.Department of Mathematics,University of Michigan,Ann Arbor,USA |
| |
Abstract: | We present a deterministic algorithm, which, for any given \(0< \epsilon < 1\) and an \(n \times n\) real or complex matrix \(A=\left( a_{ij}\right) \) such that \(\left| a_{ij}-1 \right| \le 0.19\) for all \(i, j\) computes the permanent of \(A\) within relative error \(\epsilon \) in \(n^{O\left( \ln n -\ln \epsilon \right) }\) time. The method can be extended to computing hafnians and multidimensional permanents. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|