Random path method with pivoting for computing permanents of matrices

摘要

The permanent of matrix is important in mathematics and applications. Its computation, however, is #P-complete. Randomized algorithms are natural consideration to deal with such kind of problems. A Monte Carlo algorithm for approximating permanents of matrices is proposed in this paper, which improves a method by Rasmussen. Mathematical analysis and numerical computations show the efficiency of the method.