Approximating the permanent via importance sampling with application to the dimer covering problem (Q1282386): Difference between revisions

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)].