Approximating the permanent

摘要: A randomised approximation scheme for the permanent of a 0–1s presented. The task estimating is reduced to that almost uniformly generating perfect matchings in graph; latter accomplished by simulating Markov chain whose states are graph. For wide class 0–1 matrices fully-polynomial, i.e., runs time polynomial size matrix and parameter controls accuracy output. This includes all dense (those contain sufficiently many 1’s) sparse some reasonable probabilistic model given density.For approach sketched above be computationally efficient, must rapidly mixing: informally, it converge short its stationary distribution. major portion paper devoted demonstrating mixing, apparently first such result with genuinely c...