Approximating the number of monomer-dimer coverings of a lattice
Journal of Statistical PhysicsPublished 1 May 1996
Claire Kenyon, Dana Randall, Alistair Sinclair
Citations85
SJR quartileQ2
SJR score0.67
SNIP1.00
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents the first provably polynomial-time approximation algorithms for computing the number of coverings with any specified number of monomers ind-dimensional rectangular lattice with periodic boundaries, for any fixed dimensiond, and in two-dimensional lattices with fixed boundaries.
Abstract
We study the problem of counting the number of coverings of ad-dimensional rectangular lattice by a specified number of monomers and dimers. This problem arises in several models in statistical physics, and has been widely studied. A classical technique due to Fisher, Kasteleyn, and Temperley solves the problem exactly in two dimensions when the number of monomers is zero (the dimer covering problem), but is not applicable in higher dimensions or in the presence of monomers. This paper presents the first provably polynomial-time approximation algorithms for computing the number of coverings with any specified number of monomers ind-dimensional rectangular lattices with periodic boundaries, for any fixed dimensiond, and in two-dimensional lattices with fixed boundaries. The algorithms are based on Monte Carlo simulation of a suitable Markov chain, and, in constrast to most Monte Carlo algorithms in statistical physics, have rigorously derived performance guarantees that do not rely on any assumptions. The method generalizes to counting coverings of any finite vertex-transitive graph, a class which includes most natural finite lattices with periodic boundary conditions.
Keywords
Computer ScienceMathematics
ACM SIGACT NewsApproximation Algorithms for NP-Hard Problems
3,133 Citations1997Dorit S. Hochba
This book reviews the design techniques for approximation algorithms and the developments in this area since its inception about three decades ago and the "closeness" to optimum that is achievable in polynomial time.
Theoretical Computer ScienceThe complexity of computing the permanent
2,759 Citations1979Leslie G. Valiant
It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations.
Journal of Mathematical PhysicsDimer Statistics and Phase Transitions
966 Citations1963Piet Kasteleyn
Philosophical magazineDimer problem in statistical mechanics-an exact result
827 Citations1961H. N. V. Temperley, Michael E. Fisher
SIAM Journal on ComputingApproximating the Permanent
793 Citations1989Mark Jerrum, Alistair Sinclair
A randomised approximation scheme for the permanent of a 0–1s presented, demonstrating that the matchings chain is rapidly mixing, apparently the first such result for a Markov chain with genuinely c...
SIAM Journal on ComputingPolynomial-Time Approximation Algorithms for the Ising Model
559 Citations1993Mark Jerrum, Alistair Sinclair
Computational solutions to some classical combinatorial problems in statistical physics stem from the Ising model, which has been the focus of much attention in the physics and mathematics communities since it was first introduced by Lenz and Ising in the early 1920s.
Combinatorics Probability ComputingImproved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
512 Citations1992Alistair Sinclair
A new upper bound on the mixing rate is presented, based on the solution to a multicommodity flow problem in the Markov chain viewed as a graph, and improved bounds are obtained for the runtimes of randomised approximation algorithms for various problems, including computing the permanent of a 0–1 matrix, counting matchings in graphs, and computing the partition function of a ferromagnetic Ising system.
Communications in Mathematical PhysicsTheory of monomer-dimer systems
510 Citations1972Ole J. Heilmann, Élliott H. Lieb
Communications in Mathematical PhysicsTheory of monomer-dimer systems
409 Citations1972Ole J. Heilmann, Élliott H. Lieb
Birkhäuser Boston eBooksAlgorithms for Random Generation and Counting: A Markov Chain Approach
381 Citations1993Alistair Sinclair
The Markov chain approach to generation problems and self-embeddable relations, a robust notion of approximate counting, and direct applications.
Journal of AlgorithmsMonte-Carlo approximation algorithms for enumeration problems
334 Citations1989Richard M. Karp, Michael Luby +1 more
The emphasis is on the development and analysis of a much more efficient ϵ, δ approximation algorithm for the DNF counting problem, which is substantially faster than the fastest known deterministic solution for the problem.
Transactions of the Faraday SocietyAn attempt to extend the statistical theory of perfect solutions
310 Citations1937R. H. Fowler, G. S. Rushbrooke
Physical ReviewStatistical Mechanics of Dimers on a Plane Lattice. II. Dimer Correlations and Monomers
276 Citations1963Michael E. Fisher, John Stephenson
Physical review. B, Solid stateAntiferromagnetism. The Triangular Ising Net
204 Citations1973Gregory H. Wannier
SIAM Journal on ComputingA Monte-Carlo Algorithm for Estimating the Permanent
118 Citations1993Narendra Karmarkar, Richard M. Karp +3 more
A Monte-Carlo algorithm is described that produces a “good in the relative sense” estimate of the permanent of A and has running time ${\operatorname{poly}(n)2^{{n / 2}} $, where ${\ operatornam{poly}}( n)$ denotes a function that grows polynomially with n.
Journal of Statistical PhysicsTwo-dimensional monomer-dimer systems are computationally intractable
117 Citations1987Mark Jerrum
The classic problem of counting monomer-dimer arrangements on a two-dimensional lattice is analyzed using techniques from theoretical computer science and it can be shown that the general problem is computationally intractable.
Journal of Statistical PhysicsTwo-dimensional monomer-dimer systems are computationally intractable
115 Citations1990Mark Jerrum
The classic problem of counting monomer-dimer arrangements on a two-dimensional lattice is analyzed using techniques from theoretical computer science and it can be shown that the general problem is computationally intractable.
AlgorithmicaOn the number of Eulerian orientations of a graph
94 Citations1996Milena Mihail, P. Winkler
The Monotonicity Lemma is established, which establishes the intuitive fact that increasing the number of constraints applied on a flow problem cannot increase thenumber of solutions, and the complementary hardness result, namely, that counting exactly Eulerian orientations is #P-complete is given.
Journal of Physics A Mathematical and GeneralSolution of the dimer problem on a hexagonal lattice with boundary
64 Citations1984Veit Elser
Markov chains and polynomial time algorithms
63 Citations2002Ravi Kannan
This paper outlines the use of rapidly mixing Markov Chains in randomized polynomial time algorithms to solve approximately certain counting problems.
Proceedings of the Royal Society of London A Mathematical and Physical SciencesSome properties of adsorbed films of oxygen on tungsten
57 Citations1935John K. Roberts
Journal of Statistical PhysicsCritical behavior of a three-dimensional dimer model
56 Citations1983Somendra M. Bhattacharjee, John F. Nagle +2 more
Random Structures and AlgorithmsApproximating the permanent: A simple approach
51 Citations1994Lars Eilstrup Rasmussen
An efficient and very simple unbiased estimator for the enumeration of square (0–1) matrices is presented and it is proved that this estimator runs in time polynomial in the size of the input matrix for almost all matrices.
Discrete MathematicsOn defect-d matchings in graphs
49 Citations1975Charles H. C. Little, Douglas D. Grant +1 more
It is shown that a regular graph G of degree r which is (r � 1)-edge-connected is 0-covered or 1-covered depending on whether G has an even or odd number of vertices, but, given any non-negative integers r and d, there exists a graph regular with connectivity and edge-connectivity r � 2 which does not even have a defect-d matching.
Mathematical Proceedings of the Cambridge Philosophical SocietyAn improved lower bound for the multidimensional dimer problem
35 Citations1968J. M. Hammersley
IMA Journal of Applied MathematicsA Lower Bound for the Monomer-Dimer Problem
33 Citations1970J. M. Hammersley, V. V. Menon
Mathematical Proceedings of the Cambridge Philosophical SocietyA note on the monomer dimer problem
17 Citations1966J. A. Bondy, Dominic Welsh
Expanding graphs and the average-case analysis of algorithms for matchings and related problems
15 Citations1989R. Motwani
If a graph is an expander with expansion more than one than every non-maximum matching has a short augmenting path and, therefore, the bipartite matching algorithm performs much better on such graphs than in the worst case.
A mildly exponential approximation algorithm for the permanent
13 Citations1992Mark Jerrum, Umesh Vazirani
Journal of Mathematical PhysicsNegative Finding for the Three-Dimensional Dimer Problem
11 Citations1969J. M. Hammersley, A. Feuerverger +2 more
PhysicaA cell-cluster theory for the liquid state III
11 Citations1957Eliahu Cohen, Jan de Boer +1 more
Matchings in lattice graphs
10 Citations1993Claire Kenyon, Dana Randall +1 more
This paper presents the first eficient approximation algorithms for counting matchings of arbitrary cardinality in d-dimensional rectangular lattices in any fixed dimension d; and two-dimensional lattices with “fixed boundary conditions” (i. e., no wrap-around edges).