Portal de Periódicos da CAPES

An algorithmic proof of Brégman–Minc theorem

2009; Taylor & Francis; Volume: 86; Issue: 12 Linguagem: Inglês

10.1080/00207160802441264

1029-0265

Li Xu, Heng Liang, Fengshan Bai,

Random Matrices and Applications

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.