On coupling and the approximation of the permanent (Q1115170)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On coupling and the approximation of the permanent |
scientific article |
Statements
On coupling and the approximation of the permanent (English)
0 references
1989
0 references
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.
0 references
permanent
0 references
dense 0-1 matrices
0 references
Markov chain simulation method
0 references
sampling schemes
0 references
counting algorithms
0 references
0 references