The permanent of an nxn matrix with entries is defined by
where the sum is over all permutations of
. Informally,
it similar to the determinant but without the alternating signs. However, in
contrast with the determinant, no efficient procedure for computing this
function is known. The permanent is important because it is equivalent to
counting perfect matchings of a bipartite graph and arises naturally in a
number of fields including discrete optimization, statistical physics and
scheduling. Computing the permanent is typical of the kind of combinatorial
problems that arise in data communications, a class of issues that NIST will
need to face in coming years. Based on our experience in Monte Carlo
simulation and in linear algebra we have developed an approximation algorithm
that extends the best approximation algorithm for computing the permanent
(Jerrum & Sinclair, SIAM J. Comput. v. 18) to a wider class of matrices. We
use importance sampling as a method for reducing the variance of the samples
generated and thus hasten convergence. We are developing a particularly
efficient implementation based on some little known methods of linear algebra
and plan to work on the application of this method to real problems in
physics.