On coupling and the approximation of the permanent

DOI10.1016/0020-0190(89)90115-4MaRDI QIDQ1115170zbMATH OpenOpenAlexFDO

Authors Milena Mihail

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90115-4

zbMATH Keywords

counting algorithmsdense 0-1 matricesMarkov chain simulation methodpermanentsampling schemes

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Determinants, permanents, traces, other special matrix functions (15A15) Matrices of integers (15B36) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probabilistic methods, stochastic differential equations (65C99)

Review text

An approximation algorithm for computing the permanent of dense 0-1 matrices is discussed. Possibilities and limitations are studied for the Markov chain simulation method as an approach to obtain efficient sampling schemes (and hence approximate counting algorithms), similarly as proposed by \textit{A. Broder} [How hard is it to marry at random, Proc. 18th ACM Symposium on Theory of Computing (1986))], for exponentially large populations with a nontrivial combinatorial structure. Bounding the variation distance of Markov chains is analyzed. The coupling technique and the way how it exhibits its limitations for the particular Markov chain is investigated. The Broder's Markov chain MC2 is studied especially and the construction of a coupling process C2 is attempted, C2 failure as a coupling is explained.

Recommendations

• Approximating the Permanent
• scientific article; zbMATH DE number 4131659
• scientific article; zbMATH DE number 420886
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Exact sampling from perfect matchings of dense regular bipartite graphs

Cites work

• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 3255204 (Why is no real title available?)
• On coupling of Markov chains
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• Random generation of combinatorial structures from a uniform distribution
• Strong uniform times and finite random walks

Cited in

(4)

• Computing the permanent by importance sampling method.
• An analysis of Monte Carlo algorithm for estimating the permanent
• scientific article; zbMATH DE number 4131659 (Why is no real title available?)
• scientific article; zbMATH DE number 1563189 (Why is no real title available?)

This page was built for publication: On coupling and the approximation of the permanent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1115170)