Back to Search
Start Over
Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices.
- Source :
-
Linear Algebra & its Applications . May2016, Vol. 497, p108-115. 8p. - Publication Year :
- 2016
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00243795
- Volume :
- 497
- Database :
- Academic Search Index
- Journal :
- Linear Algebra & its Applications
- Publication Type :
- Academic Journal
- Accession number :
- 113539958
- Full Text :
- https://doi.org/10.1016/j.laa.2016.02.023