The Approximate Algorithm For Sparse Permanent Based On Sequential Importance Sampling

The permanent is one of the important invariants for matrix. Its defination issimilar to the determinant of a matrix. However, the computation of the permanent ismuch harder than that of the determinant. It is proved by Valiant in1979that the exactcalculation of the permanent is a#P-complete problem.#P-complete problems are aclass of intractable counting problems, which are not easier that NP-complete problemsin combinatorial optimization. The best-known algorithm for precise evaluation of thepermanent of general matrix is O(n2^n-1) in complexity. Hence approximate algorithms,which can give a reasonable estimation for matrix permanent within an acceptablecomputer time, attract more attentions.The approximate algorithms for permanent can be divided into three categories:elementary recursive algorithms; reductions to determinants and Markov chain MonteCarlo method. Every category has its own advantage. The diferent kind of algorithmssuit for the special structure properties of the problems.The paper focuses on the computation of the matrix permanent arising from thepermutation test in statistics and dimer covering in statistical physics. The matrices aresparse and0-1valued. We adopt the sequential importance sampling and resamplingstrategies to the approximate algorithms of sparse permanents.We have achieved the following innovations：A new upper bound of the permanent is proposed;Giving the improved approximate permanent algorithm based on the optimal re-sampling strategy proposed by Fearnhead and ClifordApplying the new algorithm to the permutation test in statistics and dimer cover-ing in statistical physics, the results show the efciency of the improved strategy.