This paper makes three contributions to estimating the number of perfect matching in bipartite graphs. First, we prove that the popular sequential importance sampling algorithm works in polynomial time for dense bipartite graphs. More carefully, our algorithm gives a $(1\pm\epsilon)$-approximation for the number of perfect matchings of a $\lambda$-dense bipartite graph, using $O(n^{\frac{1-2\lambda}{\lambda}\epsilon^{-2}})$ samples. With size $n$ on each side and for $\frac{1}{2}>\lambda>0$, a $\lambda$-dense bipartite graph has all degrees greater than $(\lambda+\frac{1}{2})n$. Second, practical applications of the algorithm require many calls to matching algorithms. A novel preprocessing step is provided which makes significant improvements. Third, three applications are provided. The first is for counting Latin squares, the second is a practical way of computing the greedy algorithm for a card-guessing game with feedback, and the third is for stochastic block models. In all three examples, sequential importance sampling allows treating practical problems of reasonably large sizes.

翻译：本文为估算双面图中完美匹配的数量做出了三点贡献。 首先, 我们证明流行的连续重要抽样算法在密集双面图的多元时段中起作用。 更仔细地说, 我们的算法给出了$(1\ pm\ pm\ epsilon)$- accolation $- accessite 图形的完美匹配数量。 其次, 算法的实际应用需要许多匹配算法的呼声。 提供了一个新的预处理步骤, 从而做出重大改进 。 第三, 提供了三个应用程序。 第一个是计算拉丁方块, 第二种是计算卡片序列模型的任意性算法, 第三个是计算卡片序列模型的实用方法, 使卡片序列模型的大规模分析变得重要。