- 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.
- Links To Paper
- 1st Link
- Bibtex format
- @Article{EDI-INF-RR-0460,
- author = {
Mark Jerrum
and Alistair Sinclair
and Eric Vigoda
},
- title = {A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries},
- journal = {Journal of the ACM},
- publisher = {ACM},
- year = 2004,
- month = {Jul},
- volume = {51(4)},
- pages = {671-697},
- url = {http://doi.acm.org/10.1145/1008731.1008738},
- }
|
