A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix

David Gamarnik, Dmitriy Katz

We construct a deterministic approximation algorithm for computing a permanent of a $0,1$ $n$ by $n$ matrix to within a multiplicative factor $(1+\epsilon {)}^n$, for arbitrary $\epsilon >0$. When t…