Notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices

详细信息    查看全文

• 作者：Fanny Dufoss&eacute ; ^a ; ^{fanny.dufosse@inria.fr" class="auth_mail" title="E-mail the corresponding author} ; Bora Uç ; ar^b ; ^{bora.ucar@ens-lyon.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：15B51 ; 05C50 ; 05C70
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：15 May 2016
• 年：2016
• 卷：497
• 期：Complete
• 页码：108-115
• 全文大小：286 K

文摘

Birkhoff–von Neumann (BvN) decomposition of doubly stochastic matrices expresses a double stochastic matrix as a convex combination of a number of permutation matrices. There are known upper and lower bounds for the number of permutation matrices that take part in the BvN decomposition of a given doubly stochastic matrix. We investigate the problem of computing a decomposition with the minimum number of permutation matrices and show that the associated decision problem is strongly NP-complete. We propose a heuristic and investigate it theoretically and experimentally on a set of real world sparse matrices and random matrices.