Problems / algorithms-optimization

algorithms-optimization / Approximation algorithms

The Optimal Approximation Ratio for Permanents of PSD Matrices

What is the best deterministic polynomial-time approximation ratio for the permanent of a Hermitian positive semidefinite matrix? Resolved up to lower-order terms in the exponent: an explicit concave maximisation $\widehat P(A)$ satisfies $e^{-\gamma n}\widehat P(A) \le \mathrm{per}(A) \le \widehat P(A)$, giving a deterministic $e^{(\gamma+\varepsilon)n}$-approximation for every $\varepsilon > 0$ and matching the known $e^{(\gamma-\varepsilon)n}$ hardness, where $\gamma$ is the Euler-Mascheroni constant.