I know that for an arbitrary $n \times n$ matrix, Ryser's algorithm can compute the permanent in $\mathcal{O}(2^n n^2)$ time. I'm interested in computing the permanent of $n \times n$ matrices of rank $m$. A few sources told me that this algorithm is exponential in $m$. The algorithm must also depend on $n$, so what is the $\mathcal{O}$-notation for this? $\mathcal{O}(2^m n^2)$? $\mathcal{O}(n^m)$?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ The paper "Two algorithmic results for the traveling salesman problem" by Barvinok describes an $n^{\mathcal{O}(m)}$ algorithm for computing the permanent of a rank-$m$ matrix. I don't know whether this can be improved to $\mathrm{poly}(n) 2^{\mathcal{O}(m)}$. $\endgroup$– smapersCommented Jan 30, 2020 at 17:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The paper "Two algorithmic results for the traveling salesman problem" by Barvinok describes an $n^{\mathcal{O}(m)}$ algorithm for computing the permanent of a rank-m matrix. I don't know whether this can be improved to $\mathrm{poly}(n) 2^{\mathcal{O}(m)}$.
(I originally posted this as a comment. I post it as an answer by lack of any other answers.)
