Approximating the Permanent via Importance Sampling with Application to the Dimer Covering Problem

Ando, 1989, Majorization, doubly stochastic matrices and comparison of eigenvalues, Linear Algebra Appl., 118, 163, 10.1016/0024-3795(89)90580-6 Bapat, 1986, Applications of an inequality in information theory to matrices, Linear Algebra Appl., 78, 107, 10.1016/0024-3795(86)90018-2 Barvinok, 1997, Computing mixed discriminants, mixed volumes and permanents, Discrete Comput. Geom., 18, 205, 10.1007/PL00009316 Bregman, 1967, Proof of convergence of Sheleikhovskii's method for a problem with transportation constraints, Zh. Vychsl. Mat. Mat. Fiz., 7, 147 M. Ciucu, An improved upper bound for the three-dimensional dimer problem, to appear. Fowler, 1937, Statistical theory of perfect solutions, Trans. Faraday Soc., 33, 1271, 10.1039/tf9373301272 Frenkel, 1996, Understanding Molecular Simulation Hammersley, 1968, An improved lower bound for the multidimensional dimer problem, Proc. Camb. Phil. Soc., 64, 455, 10.1017/S030500410004305X Hammersley, 1966, Existence theorems and Monte Carlo methods for the monomer–dimer problem, Research Papers in Statistics: Festschrift for J. Neyman, 125 Hammersley, 1964, Monte Carlo Methods, 10.1007/978-94-009-5819-7 Hopcroft, 1973, An n5/2 algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 225, 10.1137/0202019 Jerrum, 1987, Two-dimensional monomer–dimer systems are computationally intractible, J. Stat. Phys., 48, 121, 10.1007/BF01010403 Jerrum, 1989, Approximating the permanent, SIAM J. Comput., 18, 1149, 10.1137/0218077 Karmarkar, 1993, A Monte Carlo algorithm for estimating the permanent, SIAM J. Comput., 22, 284, 10.1137/0222021 Kastelyn, 1961, The statistics of dimers on a lattice, Physica, 27, 1209, 10.1016/0031-8914(61)90063-5 Kenyon, 1996, Approximating the number of monomer–dimer coverings of a lattice, J. Stat. Phys., 83, 637, 10.1007/BF02183743 N. Linial, A. Samorodnitsky, and, A. Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, to appear. London, 1971, On matrices with double stochastic pattern, J. Math. Anal. Appl., 34, 648, 10.1016/0022-247X(71)90104-1 Minc, 1978, An upper bound for the multidimensional dimer problem, Math. Proc. Cambridge Philos. Soc., 83, 461, 10.1017/S0305004100054748 Minc, 1982, Review of the paper “On Lower Bounds for Permanents” by A. Schrijver and W. G. Valiant, Math Rev. Peressini, 1988, The Mathematics of Nonlinear Programming, 10.1007/978-1-4612-1025-2 Priezzhev, 1981, The statistics of dimers on a three-dimensional lattice. II. An improved lower bound, J. Stat. Phys., 829, 10.1007/BF01010944 Ryser, 1963, Carus Monographs, Combinatorial Mathematics, 14, 10.5948/UPO9781614440147 Sullivan, 1974, A descent method with smooth rotund spaces with applications to approximation in Lp, J. Math. Anal. Appl., 48, 155, 10.1016/0022-247X(74)90223-6 Sinkhorn, 1964, A relationship between arbitrary positive matrices and double stochastic matrices, Ann. Math. Stat., 35, 876, 10.1214/aoms/1177703591 Soules, 1991, The rate of convergence of Sinkhorn balancing, Linear Algebra Appl., 150, 3, 10.1016/0024-3795(91)90157-R Schrijver, 1998, Counting 1-factors in regular bipartite graphs, J. Combin. Theory B, 72, 122, 10.1006/jctb.1997.1798 Schrijver, 1980, On lower bounds for permanents, Nederl. Akad. Wetensch. Indag. Math., 42, 425, 10.1016/1385-7258(80)90043-8 Temperley, 1961, Dimer problem in statistical mechanics—An exact result, Philos. Mag., 6, 1061, 10.1080/14786436108243366