For PSD matrices with no zero diagonal, per(A) satisfies e^{-γ n}widehat{P}(A) ≤ per(A) ≤ widehat{P}(A) where widehat{P} is obtained by maximizing a concave function, giving an optimal e^{(γ+o(1))n} deterministic approximation.
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We design a deterministic polynomial time $c^n$ approximation algorithm for the permanent of positive semidefinite matrices where $c=e^{\gamma+1}\simeq 4.84$. We write a natural convex relaxation and show that its optimum solution gives a $c^n$ approximation of the permanent. We further show that this factor is asymptotically tight by constructing a family of positive semidefinite matrices.
fields
cs.DS 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Optimal $e^{(\gamma+o(1))n}$-Approximation of the Permanent of Positive Semidefinite Matrices
For PSD matrices with no zero diagonal, per(A) satisfies e^{-γ n}widehat{P}(A) ≤ per(A) ≤ widehat{P}(A) where widehat{P} is obtained by maximizing a concave function, giving an optimal e^{(γ+o(1))n} deterministic approximation.