Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
✍ Scribed by Alexander Barvinok
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 308 KB
- Volume
- 14
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
We present real, complex, and quaternionic versions of a simple randomized polynomial time algorithm to approximate the permanent of a nonnegative matrix and, more generally, the mixed discriminant of positive semidefinite matrices. The algorithm provides an unbiased estimator, which, with high probability, approximates the true value within a Ž n . Ž . factor of O c , where n is the size of the matrix matrices and where c f 0.28 for the real version, c f 0.56 for the complex version, and c f 0.76 for the quaternionic version. We discuss possible extensions of our method as well as applications of mixed discriminants to problems of combinatorial counting.