A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
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 arbitra...
| Publié dans: | Journal of the ACM 51, 4 (2004). |
|---|---|
| Auteur principal: | |
| Format: | Article |
| Langue: | anglais |
| Sujets: |