Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor This research was partially supported by Alfred P. Sloan Research Fellowship, by NSF Grants DMS 9501129 and DMS 9734138, and by the Mathematical Sciences Research Institute, Berkeley, CA through NSF Grant DMS 9022140.

Abstract

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 factor of O ( c n ), where n is the size of the matrix (matrices) and where c ≈ 0.28 for the real version, c ≈ 0.56 for the complex version, and c ≈ 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. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 29–61, 1999