Advanced search
Publication Cover
International Journal of Computer Mathematics Volume 86, 2009 - Issue 12
Submit an article Journal homepage
61
Views
0
CrossRef citations to date
0
Altmetric
Section B

An algorithmic proof of Brégman–Minc theorem

Li Xu Department of Mathematical Sciences, Tsinghua University, Beijing, P.R.China
,
Heng Liang Department of Mathematical Sciences, Tsinghua University, Beijing, P.R.ChinaCorrespondence[email protected]
&
Fengshan Bai Department of Mathematical Sciences, Tsinghua University, Beijing, P.R.China
Pages 2181-2185 | Received 16 Aug 2008, Accepted 27 Aug 2008, Published online: 18 Mar 2009

References

  • Alon , N. , Spencer , J. H. and Erdos , P. 1992 . The Probabilistic Method , New York : Wiley .
  • Beichl , I. and Sullivan , F. 1999 . Approximating the permanent via importance sampling with application to the Dimer Covering Problem . J. Comput. Phys. , 149 : 128 – 147 .
  • Brégman , L. M. 1973 . Some properties of nonnegative matrices and their permanents . Soviet Math. Dok. , 14 : 945 – 949 .
  • Brualdi , R. A. and Ryser , H. J. 1991 . Combinatorial Matrix Theory , Cambridge : Cambridge University Press .
  • Friedland , S. , Rider , B. and Zeitouni , O. 2004 . Concentration of permanent estimators for certain large matrices . Ann. Appl. Probab. , 14 ( 3 ) : 1559 – 1576 .
  • Gutman , I. 1998 . Permanents of adjacency matrices and their dependence on molecular structure . Polycyclic Arom. Compd. , 12 : 281 – 287 .
  • Huo , Y. , Liang , H. , Liu , S. and Bai , F. 2008 . Computing monomer-dimer systems through matrix permanent . Phys. Rev. E , 77 ( 1 ) : 016706
  • Jerrum , M. , Sinclair , A. and Vigoda , E. 2004 . A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries . J. ACM , 51 ( 5 ) : 671 – 697 .
  • Karmarkar , N. , Karp , R. M. , Lipton , R. , Lovasz , L. and Luby , M. 1993 . A Monte Carlo algorithm for estimating the permanent . SIAM J. Comput. , 22 : 284 – 293 .
  • Liang , H. and Bai , F. 2004 . A new upper bound for permanent of (0,1)-matrices . Linear Algebra Appl. , 277 : 291 – 295 .
  • Linial , N. , Samorodnitsky , A. and Wigderson , A. 2000 . A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents . Combinatorica , 20 : 545 – 568 .
  • Minc , H. 1963 . Upper bound for permanents of (0,1)-matrices . Bull. Amer. Math. Soc. (N.S.) , 69 : 789 – 791 .
  • Minc , H. 1978 . Permanents , Reading, MA : Addison-Wesley .
  • Radhakrishnan , J. 1997 . An entropy proof of Brégman's theorem . J. Combin. Theory Ser. A , 77 : 161 – 164 .
  • Rasmussen , L. E. 1994 . Approximating the permanent: a simple approach . Random Structures Algorithms , 5 : 349 – 361 .
  • Schrijver , A. 1978 . A short proof of Minc's conjecture . J. Combin. Theory Ser. A , 25 : 80 – 83 .
  • Valliant , L. 1979 . The complexity of computing the permanent . Theoret. Comput. Sci. , 8 : 189 – 201 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.