Approximating the permanent via importance sampling with application to the dimer covering problem
type: Item
instance of: scholarly article
title: Approximating the permanent via importance sampling with application to the dimer covering problem
zbMATH Open document ID: 0927.65065
author: K. Appert
published in: Journal of Computational Physics
publication date: 1999-11-25T00:00:00Z
review text: This paper is concerned with the dimer covering problem. Following a brief sketch of the history of the dimer covering problem, the idea of importance sampling is introduced, which plays a key role in direct sampling used in this paper. The permanent approximation algorithm using the importance function generated by the Sinkhorn balance [cf. \textit{R. Sinkhorn}, Ann. Math. Stat. 35, 876-879 (1964; Zbl 0134.25302)] is explained with notes on variance and data structures. The obtained estimate of the asymptotic growth rate of the number of dimer covers of a cubic is found to be consistent with the bounds given by \textit{J. M. Hammersley}, Research Papers Stat., Festschr. J. Neyman, 125-146 (1966; Zbl 0161.15401)] and \textit{A. Schrijver} [J. Comb. Theory, Ser. B 72, No. 1, 122-135 (1998; Zbl 0905.05060)], and \textit{M. Ciucu} [An improved upper bound for the three-dimensional dimer problem (to appear)].
reviewed by: Katsuji Uosaki
Mathematics Subject Classification ID: 65F40
Mathematics Subject Classification ID: 65C60
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 62K10
Mathematics Subject Classification ID: 65C05
zbMATH DE Number: 1271977
zbMATH Keywords: dimer covers
zbMATH Keywords: cubic lattice
zbMATH Keywords: Monte Carlo approach
zbMATH Keywords: Sinkhorn balanced matrix
zbMATH Keywords: importance sampling
zbMATH Keywords: permanent
MaRDI profile type: Publication
full work available at URL: jcph.1998.6149
OpenAlex ID: W2077135574
cites work: Majorization, doubly stochastic matrices, and comparison of eigenvalues
cites work: Applications of an inequality in information theory to matrices
cites work: Computing mixed discriminants, mixed volumes, and permanents
cites work: An improved upper bound for the \(3\)-dimensional dimer problem
cites work: Q4365276
cites work: Q5537646
cites work: Q5543146
cites work: Q5732992
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Approximating the Permanent
cites work: A Monte-Carlo Algorithm for Estimating the Permanent
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Approximating the number of monomer-dimer coverings of a lattice.
cites work: A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
cites work: On matrices with doubly stochastic pattern
cites work: An upper bound for the multidimensional dimer problem
cites work: Q3994363
cites work: Descent methods in smooth, rotund spaces with applications to approximation in L\(^p\)
cites work: A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
cites work: The rate of convergence of Sinkhorn balancing
cites work: Counting 1-factors in regular bipartite graphs
cites work: Q3897156
cites work: Dimer problem in statistical mechanics-an exact result
DOI: 10.1006/JCPH.1998.6149
description: scientific article; zbMATH DE number 1271977