Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices

Abstract: We design a deterministic polynomial time

c^{n}

approximation algorithm for the permanent of positive semidefinite matrices where

c = e^{g a m m a + 1} s i m e q 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.

This page was built for publication: Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices