A simple polynomial time algorithm to approximate the permanent within a simply exponential factor
| dc.creator | Barvinok, Alexander | |
| dc.date | 1997-04-09 | |
| dc.date.accessioned | 2026-07-07T09:15:45Z | |
| dc.date.available | 2026-07-07T09:15:45Z | |
| dc.description | We present a simple randomized polynomial time algorithm to approximate the mixed discriminant of $n$ positive semidefinite $n \times n$ matrices within a factor $2^{O(n)}$. Consequently, the algorithm allows us to approximate in randomized polynomial time the permanent of a given $n \times n$ non-negative matrix within a factor $2^{O(n)}$. When applied to approximating the permanent, the algorithm turns out to be a simple modification of the well-known Godsil-Gutman estimator. | |
| dc.identifier | https://arxiv.org/abs/math/9704218 | |
| dc.identifier | http://arxiv.org/abs/math/9704218 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/153122 | |
| dc.subject | Rings and Algebras | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | A simple polynomial time algorithm to approximate the permanent within a simply exponential factor | |
| dc.type | text |