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!


1 Answer 1


What about

Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric., A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM 51, No. 4, 671–697 (2004). ZBL1204.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, Algorithmica 32, No. 1, 157–162 (2002). ZBL0995.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.


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.