Approximating the permanent via importance sampling with application to the dimer covering problem

DOI10.1006/jcph.1998.6149zbMath0927.65065OpenAlexW2077135574MaRDI QIDQ1282386

K. Appert

Publication date: 25 November 1999

Published in: Journal of Computational Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcph.1998.6149

zbMATH Keywords

importance samplingcubic latticepermanentMonte Carlo approachdimer coversSinkhorn balanced matrix

Mathematics Subject Classification ID

Related Items (16)

A hybrid algorithm for computing permanents of sparse matrices ⋮ Numerical integration in statistical decision-theoretic methods for robust design optimization ⋮ A Sequential Importance Sampling Algorithm for Counting Linear Extensions ⋮ Sequential importance sampling for estimating expectations over the space of perfect matchings ⋮ Efficient generation of random derangements with the expected distribution of cycle lengths ⋮ Stochastic enumeration with importance sampling ⋮ On the Monomer–Dimer Problem of Some Graphs ⋮ Monomer-dimer problem on random planar honeycomb lattice ⋮ Permanents, \(\alpha\)-permanents and Sinkhorn balancing ⋮ A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes ⋮ Accelerating convergence in stochastic particle dispersion simulation codes ⋮ Scaling matrices and counting the perfect matchings in graphs ⋮ Theory of computation of multidimensional entropy with an application to the monomer-dimer problem ⋮ An algorithmic proof of Brégman–Minc theorem ⋮ On a conservative partition refinement (CPR) method for a class of two-stage stochastic programming problems ⋮ Several constants arising in statistical mechanics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The rate of convergence of Sinkhorn balancing
• Applications of an inequality in information theory to matrices
• Majorization, doubly stochastic matrices, and comparison of eigenvalues
• Computing mixed discriminants, mixed volumes, and permanents
• Counting 1-factors in regular bipartite graphs
• Approximating the number of monomer-dimer coverings of a lattice.
• Descent methods in smooth, rotund spaces with applications to approximation in L\(^p\)
• An improved upper bound for the \(3\)-dimensional dimer problem
• On matrices with doubly stochastic pattern
• The statistics of dimers on a lattice
• Approximating the Permanent
• A Monte-Carlo Algorithm for Estimating the Permanent
• An upper bound for the multidimensional dimer problem
• Dimer problem in statistical mechanics-an exact result
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents

This page was built for publication: Approximating the permanent via importance sampling with application to the dimer covering problem