<p>What about</p>
<p><em>Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric.</em>, <a href="https://doi.org/10.1145/1008731.1008738" rel="nofollow noreferrer"><strong>A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries</strong></a>, J. ACM 51, No. 4, 671–697 (2004). <a href="https://zbmath.org/?q=an:1204.65044" rel="nofollow noreferrer">ZBL1204.65044</a>.</p>
<p>?</p>
<p>If you are looking for exact algorithms, the only speedup I'm aware of is</p>
<p><em>Bax, E.; Franklin, J.</em>, <a href="https://doi.org/10.1007/s00453-001-0072-0" rel="nofollow noreferrer"><strong>A permanent algorithm with <span class="math-container">$\exp[\Omega(n^{1/3}/2\ln n)]$</span> expected speedup for 0-1 matrices</strong></a>, Algorithmica 32, No. 1, 157–162 (2002). <a href="https://zbmath.org/?q=an:0995.68190" rel="nofollow noreferrer">ZBL0995.68190</a>.</p>
<p>Which also can be used to show you can do <span class="math-container">$c^n$</span> time for <span class="math-container">$c&lt;2$</span> for sparse 0/1 matrices or the UP-hard mod 3 permanent.</p>

CC BY-SA 4.0
2010-12-22T16:31:36.033Z
2023-02-08T11:44:57.417Z
2023-02-08T11:44:57.417Z
Andreas Björklund
<p>The Idea is this:</p>

<p>The Decision problems Max Cut for graphs is APX-Hard and therefore does not have a PTAS. </p>

<p>However Dense versions of Max Cut do have a PTAS! </p>

<p>This suggest that Counting Perfect Matchings for Dense Bipartite Graphs could have some sort of speed up. </p>

<p>Does such a speedup exists in the complexity literature?</p>

<p>Further to the above, I am aware of the expectional work done on NonNegative Matrices. However I was really thinking about General matrices and expecting exponential algorithms. Of course #P is by standard complexity theory intractable! </p>

<ds.algorithms>
What is the algorithmic speed up for Counting Perfect Matchings in Dense Bipartite Graphs (equivalent to Permanent of Dense 0/1 Matrices)?
Zelah 02
# What is the algorithmic speed up for Counting Perfect Matchings in Dense Bipartite Graphs (equivalent to Permanent of Dense 0/1 Matrices)?

(Asked by: username_0 on 2010-12-22)

The Idea is this:

The Decision problems Max Cut for graphs is APX-Hard and therefore does not have a PTAS.

However Dense versions of Max Cut do have a PTAS!

This suggest that Counting Perfect Matchings for Dense Bipartite Graphs could have some sort of speed up.

Does such a speedup exists in the complexity literature?

Further to the above, I am aware of the expectional work done on NonNegative Matrices. However I was really thinking about General matrices and expecting exponential algorithms. Of course #P is by standard complexity theory intractable!

**Tags:** ds.algorithms

---

## 1 answers

### Answer by username_1 on 2010-12-22. Score: 2 | Accepted answer

What about

*Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric.*, [**A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries**](https://doi.org/10.1145/1008731.1008738), J. ACM 51, No. 4, 671–697 (2004). [ZBL1204.65044](https://zbmath.org/?q=an:1204.65044).

?

If you are looking for exact algorithms, the only speedup I'm aware of is

*Bax, E.; Franklin, J.*, [**A permanent algorithm with $\exp[\Omega(n^{1/3}/2\ln n)]$ expected speedup for 0-1 matrices**](https://doi.org/10.1007/s00453-001-0072-0), Algorithmica 32, No. 1, 157–162 (2002). [ZBL0995.68190](https://zbmath.org/?q=an:0995.68190).

Which also can be used to show you can do $c^n$ time for $c<2$ for sparse 0/1 matrices or the UP-hard mod 3 permanent.


---

