A SIMPLE POLYNOMIAL TIME ALGORITHM TO APPROXIMATE THE PERMANENT WITHIN A SIMPLY

EXPONENTIAL FACTOR

ALEXANDER BARVINOK

Abstract. We present a simple randomized polynomial time algorithm to approximate the mixed discriminant of n positive semidefinite n×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×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.