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

被引：2

作者：

Diaconis, Persi ^{[1
]}

Kolesnik, Brett ^{[2
]}

机构：

[1] Stanford Univ, Dept Math & Stat, Stanford, CA 94305 USA

[2] Univ Calif Berkeley, Dept Stat, Berkeley, CA 94720 USA

来源：

ADVANCES IN APPLIED MATHEMATICS | 2021年 / 131卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Asymptotic normality; Distributional recursion; Importance sampling; Monte Carlo methods; Perfect matchings; Randomized algorithms; RECURRENCE; PERMANENT;

D O I：

10.1016/j.aam.2021.102247

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We introduce and study randomized sequential importance sampling algorithms for estimating the number of perfect matchings in bipartite graphs. In analyzing their performance, we establish various non-standard central limit theorems. We expect our methods to be useful for other applied problems. (c) 2021 Published by Elsevier Inc.

引用

页数：41