A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

By M. Jerrum, A. Sinclair, Eric Vigoda. JACM, 2004

747 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Combinatorial Bandits (2012, background): “This, together with Lemma 2 and the positive semidefinitess of Q t , implies the claimed statement.”
Mathematical Aspects of Mixing Times in Markov Chains (2006, background): “(as input) bipartite graph [34, 36], the set of proper colorings of a given graph using a fixed number of colors [28], the number of matrices having non-negative integer entries and with prescribed row and column sums [16], etc.”
The computational complexity of linear optics (2010, methodology): “Of course, in the classical case, the ai j’s are nonnegative real numbers—which means that we can approximate Per(A) in probabilistic polynomial time, by using the celebrated algorithm of Jerrum, Sinclair, and Vigoda [37].”
The Markov chain Monte Carlo revolution (2008, background): “Three of my favorite papers (which will lead the reader into the heart of this rich literature) are the [63] analysis of the hit-and-run algorithm, the [52] analysis of the problem of approximating permanents and the [70] analysis of knapsack problems.”
Unbiased Gradient Estimation with Balanced Assignments for Mixtures of Experts (2021, background): “[17] Mark Jerrum, Alistair Sinclair, and Eric Vigoda.”