Approximating the permanent via importance sampling with application to the dimer covering problem (Q1282386): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:47, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximating the permanent via importance sampling with application to the dimer covering problem |
scientific article |
Statements
Approximating the permanent via importance sampling with application to the dimer covering problem (English)
0 references
25 November 1999
0 references
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)].
0 references
dimer covers
0 references
cubic lattice
0 references
Monte Carlo approach
0 references
Sinkhorn balanced matrix
0 references
importance sampling
0 references
permanent
0 references