A Tight Analysis of Bethe Approximation for Permanent
From MaRDI portal
Publication:5020728
DOI10.1137/19M1306142OpenAlexW3211357066MaRDI QIDQ5020728
Publication date: 7 January 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.02933
Determinants, permanents, traces, other special matrix functions (15A15) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Related Items (2)
Sequential importance sampling for estimating expectations over the space of perfect matchings ⋮ Computing permanents of complex diagonally dominant matrices and tensors
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing the permanent of (some) complex matrices
- The complexity of computing the permanent
- A short proof of Minc's conjecture
- Counting 1-factors in regular bipartite graphs
- The sample size required in importance sampling
- Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
- Computing permanents of complex diagonally dominant matrices and tensors
- Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
- Approximating the Permanent with Fractional Belief Propagation
- The Bethe Permanent of a Nonnegative Matrix
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Sequential Importance Sampling for Estimating the Number of Perfect Matchings in Bipartite Graphs: An Ongoing Conversation with Laci
- Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
- Lectures on Polytopes
- Nash Social Welfare, Matrix Permanent, and Stable Polynomials
- A generalization of permanent inequalities and applications in counting and optimization
- Efficient profile maximum likelihood for universal symmetric property estimation
- Belief Propagation, Bethe Approximation and Polynomials
- The computational complexity of linear optics
- Mathematical Foundations of Computer Science 2005
- Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- An entropy proof of Bregman's theorem
This page was built for publication: A Tight Analysis of Bethe Approximation for Permanent
