An algorithmic proof of Brégman–Minc theorem

Abstract

Brégman-Minc theorem gives the best known upper bound of the permanent of (0, 1)-matrices. A new proof of the theorem is presented in this paper, using an unbiased estimator of permanent [L.E. Rasmussen, Approximating the permanent: a simple approach, Random Structures Algorithms 5 (1994), p. 349]. This proof establishes a connection between the randomized approximate algorithm and the bound estimation for permanents.

Keywords:

• permanent
• (0, 1)-matrix
• upper bound
• algorithm

2000 AMS Subject Classification :

• 15A15
• 15A45

Acknowledgements

This research is supported by National Science Foundation of China 10501030.