On coupling and the approximation of the permanent
type: Item
instance of: scholarly article
title: On coupling and the approximation of the permanent
zbMATH Open document ID: 0663.65149
DOI: 10.1016/0020-0190(89)90115-4
author: Milena Mihail
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 65C99
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 60J10
zbMATH DE Number: 4084969
zbMATH Keywords: permanent
zbMATH Keywords: dense 0-1 matrices
zbMATH Keywords: Markov chain simulation method
zbMATH Keywords: sampling schemes
zbMATH Keywords: counting algorithms
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90115-4
OpenAlex ID: W1970199091
cites work: Q3660628
cites work: On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
cites work: Strong uniform times and finite random walks
cites work: Q5541610
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: On coupling of Markov chains
description: scientific article; zbMATH DE number 4084969