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?


1 Answer 1


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

  • $\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
    Commented Sep 15, 2023 at 6:00

Your Answer

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

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