There exists FPRAS for the permanent of a matrix with nonnegative entries

Algebra, Mathematics of Computation 1 Minute

You need to know: Permutation of \{1, 2,\dots, n\}, notation P[B] for the probability of event B, polynomial algorithm, randomised algorithm.

Background: Let A be an n\times n matrix with entries a(i,j), \, i=1,\dots, n, \, j=1,\dots, n. The permanent of A is \text{per}(A) = \sum\limits_\sigma \prod\limits_{i=1}^n a(i, \sigma(i)), where the sum is over all permutations \sigma of \{1, 2,\dots, n\}. A fully polynomial randomised approximation scheme (FPRAS) for the permanent is a randomised algorithm which, given n\times n matrix A and \epsilon\in(0,1] as an input, runs in time polynomial in n and \epsilon^{-1}, and outputs a (random) number Z such that P[\exp(-\epsilon) Z \leq \text{per}(A) \leq \exp(\epsilon)Z] \geq \frac{3}{4}.

The Theorem: In August 2003, Mark Jerrum, Alistair Sinclair, and Eric Vigoda submitted to the Journal of the ACM a paper in which they proved the existence of a fully polynomial randomised approximation scheme (FPRAS) for the permanent of an arbitrary n \times n matrix A with non-negative entries.

Short context: The evaluation of the permanent of a matrix is an old well-studied problem going back as far as, at least, the 1812 memoirs of Binet and Cauchy. In 1979, Valiant proved that the permanent cannot be computed exactly and efficiently (unless a well-believed conjecture is false). The Theorem, however, states that if entries of matrix A are non-negative, then we can compute an arbitrarily close approximation to its permanent in time that depends polynomially on the input size and the desired error. Given the Valiant’s result, this is the best we could hope for.

Links: The original paper is available here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment