Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

Author(s)

Isabel M. Beichl, F Sullivan

Abstract

We estimate the asymptotic growth rate of the number of dimer covers of cubic lattice. Our estimate λ3 = 0.4466 {plus or minus} 0.0006 is consistent with the lower bound obtained by Hammersley and the more recent improved upper bound obtained by Ciucu. It is well known that computing λ is equivalent ot computing the permanent of a certain 0 - 1 matrix. We describe an extremely efficient Monte Carlo algorithm for approximating the permanent. Previous work on Monte Carlo approaches includes the pioneering results of Jerrum and Sinclair, who use a rapidly mixing random walk. Our method is inspired by results of Soules on the convergence of Sinkhorn balancing. We use balancing to generate an importance function that allows us to do direct random sampling, rather than a random walk that converges to a limiting distribution.
Citation
Journal of Computational Physics
Volume
149
Issue
No. 1

Keywords

approximation methods, dimer covering problem, discrete mathematics, Monte Carlo, statistical physics

Citation

Beichl, I. and Sullivan, F. (1999), Approximating the Permanent via Importance Sampling With Application to the Dimer Covering Problem, Journal of Computational Physics (Accessed April 25, 2024)
Created February 1, 1999, Updated February 17, 2017