Mark Jerrum
Alistair Sinclair
Skip Abstract Section
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.
- Aldous, D. 1987. On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Prob. Eng. Inf. Sci. 1, 33--46.Google Scholar
- Alon, N., and Spencer, J. 1992. The Probabilistic Method. Wiley, New York.Google Scholar
- Barvinok, A. 1999. Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor. Ran. Struct. Algor. 14, 29--61. Google Scholar
- Broder, A. Z. 1986. How hard is it to marry at random? (On the approximation of the permanent). In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 50--58. (Erratum in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, p. 551.) Google Scholar
- Chien, S., Rasmussen, L., and Sinclair, A. 2002. Clifford algebras and approximating the permanent. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, New York, 222--231. Google Scholar
- Diaconis, P., and Saloff-Coste, L. 1993. Comparison theorems for reversible Markov chains. Ann. Appl. Prob. 3, 696--730.Google Scholar
- Diaconis, P., and Stroock, D. 1991. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 36--61.Google Scholar
- Gillman, D. 1998. A Chernoff bound for random walks on expander graphs. SIAM J. Comput. 27, 1203--1220. Google Scholar
- Jerrum, M. 2003. Counting, sampling and integrating: Algorithms and complexity. In Lectures in Mathematics---ETH Zürich. Birkhäuser, Basel.Google Scholar
- Jerrum, M., and Sinclair, A. 1989. Approximating the permanent. SIAM J. Comput. 18, 1149--1178. Google Scholar
- Jerrum, M., and Sinclair, A. 1990. Fast uniform generation of regular graphs. Theoret. Comput. Sci. 73, 91--100. Google Scholar
- Jerrum, M., and Sinclair, A. 1996. The Markov chain Monte Carlo method: An approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems (Dorit Hochbaum, ed.). PWS Publishing, 482--520. Google Scholar
- Jerrum, M., Valiant, L., and Vazirani, V. 1986. Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169--188. Google Scholar
- Jerrum, M., and Vazirani, U. 1996. A mildly exponential approximation algorithm for the permanent. Algorithmica 16, 392--401.Google Scholar
- 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.Google Scholar
- Kenyon, C., Randall, D., and Sinclair, A. 1996. Approximating the number of dimer coverings of a lattice. J. Stat. Phys. 83, 637--659.Google Scholar
- Lezaud, P. 1998. Chernoff-type bounds for finite Markov chains. Ann. Appl. Prob. 8, 849--867.Google Scholar
- Linial, N., Samorodnitsky, A., and Wigderson, A. 2000. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica 20, 545--568.Google Scholar
- Mihail, M., and Winkler, P. 1992. On the number of Eulerian orientations of a graph. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 138--145. Google Scholar
- Minc, H. 1982. Permanents. Encyclopedia of Mathematics and Its Applications Vol. 6, Addison-Wesley, Reading, Mass.Google Scholar
- Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press, Cambridge, Mass. Google Scholar
- Ryser, H. J. 1963. Combinatorial Mathematics. The Carus Mathematical Monographs No. 14, Mathematical Association of America.Google Scholar
- Schweinsberg, J. 2002. An O(n2) bound for the relaxation time of a Markov chain on cladograms. Rand. Struct. Algor. 20, 59--70. Google Scholar
- Sinclair, A. 1992. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing 1, 351--370.Google Scholar
- Tutte, W. T. 1954. A short proof of the factor theorem for finite graphs. Canad. J. Math. 6, 347--352.Google Scholar
- Valiant, L. G. 1979. The complexity of computing the permanent. Theoret. Comput. Sci. 8, 189--201.Google Scholar
Index Terms
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
Recommendations
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computingWe present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries.
Pseudo-marginal Markov Chain Monte Carlo for Nonnegative Matrix Factorization
A pseudo-marginal Markov chain Monte Carlo (PMCMC) method is proposed for nonnegative matrix factorization (NMF). The sampler jointly simulates the joint posterior distribution for the nonnegative matrices and the matrix dimensions which indicate the ...
Quadratic nonnegative matrix factorization
In Nonnegative Matrix Factorization (NMF), a nonnegative matrix is approximated by a product of lower-rank factorizing matrices. Most NMF methods assume that each factorizing matrix appears only once in the approximation, thus the approximation is ...
Comments