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.
Because computing the permanent is related to counting perfect matchings, the paper by Bayati and Nair @cite_47 on counting matchings in graphs with the help of the SPA is very relevant. Note that their setup is such that the perfect matching case can be seen as a limiting case (namely the zero-temperature limit) of the matching setup. However, for the perfect matching case (a case for which the authors of @cite_47 make no claims) the convergence proof of the SPA in @cite_47 is incomplete. Moreover, their matchings are weighted only inasmuch as the weight of a matching depends on the size of the matching. Consequently, because all perfect matchings have the same size, they all are assigned the same weight. (See also the related paper by Bayati, Gamarnik, Katz, Nair, and Tet ali @cite_24 , and an extension to counting perfect matchings in certain types of graph by Gamarnik and Katz @cite_89 .) For an SPA convergence analysis of a slightly generalized weighted matching setup, the interested reader is referred to a recent paper by Williams and Lau @cite_30 .
@cite_24 @cite_47 @cite_30 @cite_89
1991832118 1986705527 1999425090 1972778238
We consider the problem of computing the permanent of a 0,1n by n matrix. For a class of matrices corresponding to constant degree expanders we construct a deterministic polynomial time approximation algorithm to within a multiplicative factor ([email protected])^n, for arbitrary @e>0. This is an improvement over the best known approximation factor e^n obtained in Linial, Samorodnitsky and Wigderson (2000) [9], though the latter result was established for arbitrary non-negative matrices. Our results use a recently developed deterministic approximation algorithm for counting partial matchings of a graph (Bayati, Gamarnik, Katz, Nair and Tet ali (2007) [2]) and Jerrum-Vazirani method (Jerrum and Vazirani (1996) [8]) of approximating permanent by near perfect matchings. The random assignment problem asks for the minimum-cost perfect matching in the complete n  n bipartite graph Knn with i.i.d. edge weights, say uniform on [0, 1]. In a remarkable work by Aldous [Aldous, D. 2001. The (2) limit in the random assignment problem. RSA18 381--418], the optimal cost was shown to converge to (2) as n  , as conjectured by Mezard and Parisi [Mezard, M., G. Parisi. 1987. On the solution of the random link matching problem. J. Phys.48 1451--1459] through the so-called cavity method. The latter also suggested a nonrigorous decentralized strategy for finding the optimum, which turned out to be an instance of the belief propagation (BP) heuristic discussed by Pearl [Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco]. In this paper we use the objective method to analyze the performance of BP as the size of the underlying graph becomes large. Specifically, we establish that the dynamic of BP on Knn converges in distribution as n   to an appropriately defined dynamic on the Poisson weighted infinite tree, and we then prove correlation decay for this limiting dynamic. As a consequence, we obtain that BP finds an asymptotically correct assignment in O(n2) time only. This contrasts with both the worst-case upper bound for convergence of BP derived by [Bayati, M., D. Shah, M. Sharma. 2008. Max-product for maximum weight matching: Convergence, correctness, and LP duality. IEEE Trans. Inform. Theory54(3) 1241--1251.] and the best-known computational cost of (n3) achieved by Edmonds and Karp's algorithm [Edmonds, J., R. Karp. 1972. Theoretical improvements in algorithmic efficiency for networ Let G = G(AB,AB), with |A| = |B| = n, be a weighted bipartite graph, and let d(,) be the cost function on the edges. Let w(M) denote the weight of a matching in G, and M* a minimum-cost perfect matching in G. We call a perfect matching M c-approximate, for c  1, if w(M)  c  w(M*). We present three approximation algorithms for computing minimum-cost perfect matchings in G. First, we consider the case when d(,) is a metric. For any  > 0, we present an algorithm that, in O(n2+ log n log2(1 )) time, computes a O(1 )-approximate matching of G, where  = log3 2  0.631. Next, we assume the existence of a dynamic data structure for answering approximate nearest neighbor (ANN) queries under d(). Given two parameters e, d e) is the query and update time of an (e 2)-ANN data structure. Finally, we present an algorithm that works even if d(,) is not a metric but admits an ANN data structure for d(,). In particular, we present an algorithm that computes, in O(e---1n3 2 (n, e) log4(n e) log ) time, a (1 + e)-approximate matching of A and B; here  is the ratio of the largest to the smallest-cost edge in G, and  (n, e) is the query and update time of an (e c)-ANN data structure for some constant c > 1. We show that our results lead to faster matching algorithms for many geometric settings. Let G=(U, V, E) be a bipartite graph with |U|=|V|=n. The factor size of G, f, is the maximum number of edge disjoint perfect matchings in G. We characterize the complexity of counting the number of perfect matchings in classes of graphs parameterized by factor size. We describe the simple algorithm, which is an approximation algorithm for the permanent that is a natural simplification of the algorithm suggested by Broder (1986) and analyzed by Jerrum and Sinclair (1988a, b). Compared to the algorithm by Jerrum and Sinclair (1988a, b), the simple algorithm achieves a polynomial speed up in the running time to compute the permanent. A combinatorial lemma is used to prove that the simple algorithm runs in time nO(n f). Thus: (1) for all constants >0, the simple algorithm runs in polynomial time for graphs with factor size at least n; (2) for some constant c, the simple algorithm is the fastest known approximation for graphs with factor size at least c log n. (Compare with the approximation algorithms described in Karmarkar (1988).) We prove the following complementary hardness results. For functions f such that 3f(n)n3, the exact counting problem for f(n)-regular bipartite graphs is #P-complete. For and e>0, for any function f such that 3f(n)n1e, approximate counting for f(n)-regular bipartite graphs is as hard as approximate counting for all bipartite graphs. An announcement of these results appears in Dagum (1988).