Sequential Importance Sampling for Estimating the Number of Perfect Matchings in Bipartite Graphs: An Ongoing Conversation with Laci

DOI10.1007/978-3-662-59204-5_6zbMath1443.05156OpenAlexW3004577485MaRDI QIDQ3295267

Persi Diaconis

Publication date: 8 July 2020

Published in: Bolyai Society Mathematical Studies (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-59204-5_6

zbMATH Keywords

permanentBrégman's inequality

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Asymptotic enumeration (05A16)

Related Items

Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs, Sequential importance sampling for estimating expectations over the space of perfect matchings, Sequential importance sampling for multiresolution Kingman-Tajima coalescent counting, Permanental generating functions and sequential importance sampling, A Tight Analysis of Bethe Approximation for Permanent

Cites Work

• Unnamed Item
• Unnamed Item
• The sample size required in importance sampling
• A proof of Tomescu's graph coloring conjecture
• A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Mathematics and Computer Science: Coping with Finiteness
• Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
• On the Switch Markov Chain for Perfect Matchings
• Statistical problems involving permutations with restricted positions
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Monte Carlo strategies in scientific computing