text: It has recently been observed that the permanent of a nonnegative square matrix, i.e., of a square matrix containing only nonnegative real entries, can very well be approximated by solving a certain Bethe free energy function minimization problem with the help of the sum-product algorithm. We call the resulting approximation of the permanent the Bethe permanent. In this paper, we give reasons why this approach to approximating the permanent works well. Namely, we show that the Bethe free energy function is convex and that the sum-product algorithm finds its minimum efficiently. We then discuss the fact that the permanent is lower bounded by the Bethe permanent, and we comment on potential upper bounds on the permanent based on the Bethe permanent. We also present a combinatorial characterization of the Bethe permanent in terms of permanents of so-called lifted versions of the matrix under consideration. Moreover, we comment on possibilities to modify the Bethe permanent so that it approximates the permanent even better, and we conclude the paper with some observations and conjectures about permanent-based pseudocodewords and permanent-based kernels.
  @cite_62: 
  @cite_6: Given non-negative weights wS on the k-subsets S of a km-element set V, we consider the sum of the products wS1 â â â wSm over all partitions V = S1 âa â â â âaSm into pairwise disjoint k-subsets Si. When the weights wS are positive and within a constant factor of each other, fixed in advance, we present a simple polynomial-time algorithm to approximate the sum within a polynomial in m factor. In the process, we obtain higher-dimensional versions of the van der Waerden and Bregman-Minc bounds for permanents. We also discuss applications to counting of perfect and nearly perfect matchings in hypergraphs.
  @cite_49: We consider the set Σ(R,C) of all m×n matrices having 0–1 entries and prescribed row sums R=(r1,…,rm) and column sums C=(c1,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0–1 matrices with prescribed row and column sums and assigned zeros in some positions.
summary: The present paper has some similarities with recent papers by Barvinok on counting zero one matrices with prescribed row and column sums @cite_49 and by Barvinok and Samorodnitsky on computing the partition function for perfect matchings in hypergraphs @cite_6 . However, these papers pursue what would be called a mean-field theory approach in the physics literature @cite_62 . An exception to the previous statement is Section 3.2 in @cite_49 , which contains Bethe-approximation-type computations. (See the references in that section for further papers that investigate similar approaches.)