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

ABSTRACT

We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary n × n matrix with nonnegative entries. This algorithm---technically a "fully-polynomial randomized approximation scheme"---computes an approximation that is, with high probability, within arbitrarily small specified relative error of the true value of the permanent.

REFERENCES

• 1: Aldous, D. 1987. On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Prob. Eng. Inf. Sci. 1, 33--46.
• 2: Alon, N., and Spencer, J. 1992. The Probabilistic Method. Wiley, New York.
• 3: Alexander Barvinok, Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, Random Structures & Algorithms, v.14 n.1, p.29-61, Jan. 1999 [doi>10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X]
• 4: A Z Broder, How hard is it to marry at random? (On the approximation of the permanent), Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.50-58, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12136]
• 5: Steve Chien , Lars Rasmussen , Alistair Sinclair, Clifford algebras and approximating the permanent, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509944]
• 6: Diaconis, P., and Saloff-Coste, L. 1993. Comparison theorems for reversible Markov chains. Ann. Appl. Prob. 3, 696--730.
• 7: Diaconis, P., and Stroock, D. 1991. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 36--61.
• 8: David Gillman, A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing, v.27 n.4, p.1203-1220, Aug. 1998 [doi>10.1137/S0097539794268765]
• 9: Jerrum, M. 2003. Counting, sampling and integrating: Algorithms and complexity. In Lectures in Mathematics---ETH Zürich. Birkhäuser, Basel.
• 10: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 11: M. Jerrum , A. Sinclair, Fast uniform generation of regular graphs, Theoretical Computer Science, v.73 n.1, p.91-100, June 1990 [doi>10.1016/0304-3975(90)90164-D]
• 12: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 13: M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
• 14: Jerrum, M., and Vazirani, U. 1996. A mildly exponential approximation algorithm for the permanent. Algorithmica 16, 392--401.
• 15: Kasteleyn, P. W. 1961. The statistics of dimers on a lattice, I., The number of dimer arrangements on a quadratic lattice. Physica 27, 1664--1672.
• 16: Kenyon, C., Randall, D., and Sinclair, A. 1996. Approximating the number of dimer coverings of a lattice. J. Stat. Phys. 83, 637--659.
• 17: Lezaud, P. 1998. Chernoff-type bounds for finite Markov chains. Ann. Appl. Prob. 8, 849--867.
• 18: Linial, N., Samorodnitsky, A., and Wigderson, A. 2000. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica 20, 545--568.
• 19: Milena Mihail , Peter Winkler, On the number of Eularian orientations of a graph, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.138-145, September 1992, Orlando, Florida, United States
• 20: Minc, H. 1982. Permanents. Encyclopedia of Mathematics and Its Applications Vol. 6, Addison-Wesley, Reading, Mass.
• 21: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 22: Ryser, H. J. 1963. Combinatorial Mathematics. The Carus Mathematical Monographs No. 14, Mathematical Association of America.
• 23: Jason Schweinsberg, An O(n²) bound for the relaxation time of a Markov chain on cladograms, Random Structures & Algorithms, v.20 n.1, p.59-70, January 2002 [doi>10.1002/rsa.10000]
• 24: Sinclair, A. 1992. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing 1, 351--370.
• 25: Tutte, W. T. 1954. A short proof of the factor theorem for finite graphs. Canad. J. Math. 6, 347--352.
• 26: Valiant, L. G. 1979. The complexity of computing the permanent. Theoret. Comput. Sci. 8, 189--201.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes; Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
Markov chain Monte Carlo, permanent of a matrix, rapidly mixing Markov chains