ABSTRACT
We describe a novel Monte Carlo method for estimating the total number of matchings, both perfect and partial, in a bi-partite graph. For the case of perfect matchings, this is equivalent to estimating the permanent of a matrix of zeros and ones. Our method is quite different from the Monte Carlo Markov Chain (MCMC) techniques that have been developed extensively in the past several years [7, 9]. Instead of using a Markov chain, an importance sampling method originally developed by Knuth [10] has been extended to apply to this class of problems. The robustness of our technique is based on the use of Sinkhorn balancing [11, 12] to construct an extremely good importance function.
