Name
Title | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1145/1008731.1008738 | J. ACM |
Keywords | Field | DocType |
permanent of a matrix,polynomial-time approximation algorithm,polynomial-time randomized algorithm,markov chain monte carlo,high probability,n matrix,small specified relative error,rapidly mixing markov chains,nonnegative entry,fully-polynomial randomized approximation scheme,true value,arbitrary n | Randomized algorithm,Discrete mathematics,Combinatorics,Markov chain Monte Carlo,Computer science,Matrix (mathematics),Polynomial time approximation algorithm | Journal |
Volume | Issue | ISSN |
51 | 4 | 0004-5411 |
ISBN | Citations | PageRank |
1-58113-349-9 | 300 | 26.29 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| mark jerrum | 1 | 2755 | 564.62 |
| Alistair Sinclair | 2 | 1506 | 308.40 |
| Eric Vigoda | 3 | 747 | 76.55 |