3
$\begingroup$

Is there a faster ($O(a^n)$ at $a<2$ or quasiP or poly) algorithm for permanent of doubly stochastic matrix compared to an arbitrary $0/1$ permanent?

Is there at least a deterministic polynomial time approximation scheme for doubly stochastic matrices?

In other words is handling of doubly stochastic matrix permanent any easier compared to an arbitrary $0/1$ matrix permanent?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Van der Waerden's conjecture, proved by Egorychev and Falikman, gives a lower bound on the value of the permanent of doubly stochastic matrices.

Linial,Samorodnitsky and Widgerson (2000) use that to develop a deterministic method to approximate the permanent of doubly stochastic matrices or matrices that are close to being doubly stochastic.

Look at the paper,

Linial, Nathan; Samorodnitsky, Alex; Wigderson, Avi A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica 20 (2000), no.4, 545–568.

Available here: https://www.cs.huji.ac.il/~nati/PAPERS/alex_perm.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ dont think this answers ds matrices are any easier as same method can be used to approximate any 0/1 matrix permanent. $\endgroup$
    – Turbo
    Sep 15 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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