Polynomial-Time Approximation of the Permanent *

Abstract Despite its apparent similarity to the (easily-computable) determinant, it is believed that there is no polynomial-time algorithm for computing the permanent of an arbitrary matrix. In this survey, we review the known approaches for efficiently estimating the permanent and discuss their relative merits and limits. Emphasis is placed on the most successful approach to date, which is based on random sampling via Markov chains. In particular, we review the historical developments that lead to a result of Jerrum, Sinclair, and Vigoda, which states that the permanent of an arbitrary matrix with non-negative entries can be approximated in polynomial time. We describe a number of techniques that were developed for this specific problem and have since been generalized to become standard techniques in the area. We assume some familiarity with complexity classes (such as P and NP), as well as a rudimentary understanding of Markov chains