Approximating the number of monomer-dimer coverings in periodic lattices.
Our starting point is an algorithm of Kenyon, Randall, and Sinclair, which is built upon the ideas of Jerrum and Sinclair, giving an approximation to crucial parameters of the monomer-dimer covering problem in polynomial time. We make two key improvements to their algorithm: we greatly reduce the number of simulations that must be run by estimating good values of the generating function parameter, and we greatly reduce the number of steps that must be taken in each simulation by aggregating to a simulation with at most five states. The result is an algorithm that is computationally feasible for modestly sized meshes. We use our algorithm on two- and three-dimensional problems, computing approximations to the coefficients of the generating function and some limiting values.
Beichl
I
I
National Institute of Standards and Technology, Gaithersburg, Maryland 20899, USA.
O'Leary
D P
DP
Sullivan
F
F