A simple polynomial time algorithm to approximate the permanent within a simply exponential factor

1997/04/09 by Alexander Barvinok, Barvinok, Alexander
Decision Sciences · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Approximation and Integration #Probabilistic and Robust Engineering Design #Rings and Algebras (math.RA)

paper · pdf · doi:10.48550/arxiv.math/9704218

openalex publication_date 1997/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Computing the permanent of (some) complex matrices
• Approximating the Permanent via Nonabelian Determinants
• Simply Exponential Approximation of the Permanent of Positive\n Semidefinite Matrices
• Approximating the Permanent of a Random Matrix with Vanishing Mean
• A Polynomial-time Algorithm for Computing the Permanent in GF(3^q)