Skip to Main content Skip to Navigation
Journal articles

Notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices

Fanny Dufossé 1 Bora Uçar 2, 3 
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Saturday, April 23, 2016 - 9:46:12 PM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM
Long-term archiving on: : Tuesday, November 15, 2016 - 10:57:29 AM


Files produced by the author(s)



Fanny Dufossé, Bora Uçar. Notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices. Linear Algebra and its Applications, Elsevier, 2016, 497, pp.108--115. ⟨10.1016/j.laa.2016.02.023⟩. ⟨hal-01270331v6⟩



Record views


Files downloads