Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs

Brett Kolesnik

(UC Berkeley)

Please LOG IN to view the video.

Date: February 5, 2019


Sequential importance sampling is a widely used technique for Monte Carlo evaluation of intractable counting and statistical problems. Matchings have seen a huge resurgence due to their appearance in, for example, donor matching of organ transplants and ride sharing `a la Lyft/Uber where drivers are matched with customers. While there are efficient methods for determining if a bipartite graph has a perfect matching, counting the number of perfect matchings is a difficult problem in general. In this talk, we introduce novel randomized sequential importance sampling algorithms for estimating the number of perfect matchings in bipartite graphs. A key to evaluating the efficiency of these algorithms is limit theory for random variables satisfying distributional recurrence relations of divide-and-conquer type. For various test graphs, our importance sampling algorithms outperform the celebrated polynomial Markov chain Monte Carlo algorithms of Jerrum, Sinclair and Vigoda within a range of interest. We think our methods should also be useful for a variety of applied problems, such as counting and testing for contingency tables and graphs with given degree sequence.

This is joint work with Persi Diaconis.


Created: Thursday, February 7th, 2019