Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices

We design a deterministic polynomial time cn approximation algorithm for the permanent of positive semidefinite matrices where c=eγ+1simeq 4.84. We write a natural convex relaxation and show that its optimum solution gives a cn approximation of the permanent. We further show that this factor is asymptotically tight by constructing a family of positive semidefinite matrices.