A deterministic $(1+\epsilon {)}^n$ approximation for the permanent of a nonnegative matrix

Abstract

For every fixed $0<\epsilon \le 1$, we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix $A\in {\mathbb{R}}_{\ge 0}^{n\times n}$, returns $Q$ satisfying $\mathrm{per}A\le Q\le (1+\epsilon {)}^n\mathrm{per}A$.