<p>Van der Waerden's conjecture, proved by Egorychev and Falikman, gives a lower bound on the value of the permanent of doubly stochastic matrices.</p>
<p>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.</p>
<p>Look at the paper,</p>
<p>Linial, Nathan; Samorodnitsky, Alex; Wigderson, Avi
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents.
Combinatorica 20 (2000), no.4, 545–568.</p>
<p>Available here: <a href="https://www.cs.huji.ac.il/%7Enati/PAPERS/alex_perm.pdf" rel="nofollow noreferrer">https://www.cs.huji.ac.il/~nati/PAPERS/alex_perm.pdf</a></p>

CC BY-SA 4.0
2023-09-15T06:00:32.917Z
dont think this answers ds matrices are any easier as same method can be used to approximate any 0/1 matrix permanent.
Turbo
CC BY-SA 4.0
2023-09-15T04:21:20.727Z
2023-09-15T04:21:20.727Z
ricardorr
<p>Is there a faster (<span class="math-container">$O(a^n)$</span> at <span class="math-container">$a&lt;2$</span> or quasiP or poly) algorithm for permanent of doubly stochastic matrix compared to an arbitrary <span class="math-container">$0/1$</span> permanent?</p>
<p>Is there at least a deterministic polynomial time approximation scheme for doubly stochastic matrices?</p>
<p>In other words is handling of doubly stochastic matrix permanent any easier compared to an arbitrary <span class="math-container">$0/1$</span> matrix permanent?</p>

<permanent>
Permanent of doubly stochastic matrix
Turbo
# Permanent of doubly stochastic matrix

(Asked by: username_0 on 2023-09-15)

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?

**Tags:** permanent

---

## 1 answers

### Answer by username_1 on 2023-09-15. Score: 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](https://www.cs.huji.ac.il/%7Enati/PAPERS/alex_perm.pdf)

> **Comments:**
> **username_0**: dont think this answers ds matrices are any easier as same method can be used to approximate any 0/1 matrix permanent.  

---

