SEQUENTIAL IMPORTANCE SAMPLING FOR ESTIMATING EXPECTATIONS OVER THE SPACE OF PERFECT MATCHINGS

• 成果类型: Article
• 署名作者: Alimohammadi, Yeganeh; Diaconis, Persi; Roghani, Mohammad; Saberi, Amin
• 署名单位: Stanford University; Stanford University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1834
• 发表日期: 2023
• 页码: 799-833
• 关键词: permanent

摘要

This paper makes three contributions to estimating the number of per-fect 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 +/- e)-approximation for the number of perfect matchings of a A.-dense bipartite graph, using O (n 1-2A. A. E-2 ) samples. With size n on each side and for 21 > A. > 0, a A.-dense bipartite graph has all degrees greater than (A. + 21)n. Second, practical applications of the algorithm requires 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.