A Tight Analysis of Bethe Approximation for Permanent

DOI10.1137/19M1306142MaRDI QIDQ5020728zbMATH OpenOpenAlexFDO

Authors Nima Anari, Alireza Rezaei

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

zbMATH Keywords

approximation algorithmsBethedeterministic algorithmsmatchingpermanent

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Determinants, permanents, traces, other special matrix functions (15A15) Combinatorial probability (60C05) Approximation algorithms (68W25)

Cites work

• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• A generalization of permanent inequalities and applications in counting and optimization
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• A short proof of Minc's conjecture
• An entropy proof of Bregman's theorem
• Approximate profile maximum likelihood
• Approximating the permanent with fractional belief propagation
• Belief Propagation, Bethe Approximation and Polynomials
• Computing permanents of complex diagonally dominant matrices and tensors
• Computing the permanent of (some) complex matrices
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• Counting 1-factors in regular bipartite graphs
• Efficient profile maximum likelihood for universal symmetric property estimation
• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 2061729 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 7250159 (Why is no real title available?)
• Lectures on Polytopes
• Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Mathematical Foundations of Computer Science 2005
• Nash social welfare, matrix permanent, and stable polynomials
• Sequential importance sampling for estimating the number of perfect matchings in bipartite graphs: an ongoing conversation with Laci
• The Bethe Permanent of a Nonnegative Matrix
• The complexity of computing the permanent
• The computational complexity of linear optics
• The sample size required in importance sampling
• Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices

Cited in

(2)

• Computing permanents of complex diagonally dominant matrices and tensors
• Sequential importance sampling for estimating expectations over the space of perfect matchings

Describes a project that uses

Uses Software

• PML

This page was built for publication: A Tight Analysis of Bethe Approximation for Permanent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5020728)