7
$\begingroup$

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)$?

$\endgroup$
  • 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$ – smapers Jan 30 at 17:59
6
$\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)}$.

(I originally posted this as a comment. I post it as an answer by lack of any other answers.)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.