Degree-$M$ Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-negative Matrix

Yuwen Huang, Navin Kashyap, Pascal O. Vontobel

The permanent of a non-negative square matrix can be well approximated by finding the minimum of the Bethe free energy functions associated with some suitably defined factor graph;…