Structural Corrections to the Bethe Approximation of the Permanent

Ijay Narang, Will Perkins

We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight ana…