Skip to Main content Skip to Navigation
New interface
Journal articles

Further notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices

Fanny Dufossé 1 Kamer Kaya 2 Ioannis Panagiotas 3 Bora Uçar 4 
1 DATAMOVE - Data Aware Large Scale Computing
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : The well-known Birkhoff-von Neumann (BvN) decomposition expresses a doubly stochastic matrix as a convex combination of a number of permutation matrices. For a given doubly stochastic matrix, there are many BvN decompositions, and finding the one with the minimum number of permutation matrices is NP-hard. There are heuristics to obtain BvN decompositions for a given doubly stochastic matrix. A family of heuristics are based on the original proof of Birkhoff and proceed step by step by subtracting a scalar multiple of a permutation matrix at each step from the current matrix, starting from the given matrix. At every step, the subtracted matrix contains nonzeros at the positions of some nonzero entries of the current matrix and annihilates at least one entry, while keeping the current matrix nonnegative. Our first result, which supports a claim of Brualdi [Canad. Math. Bull. 25 (1982), pp. 191–199], shows that this family of heuristics can miss optimal decompositions. We also investigate the performance of two heuristics from this family theoretically.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Wednesday, October 17, 2018 - 12:32:48 PM
Last modification on : Tuesday, October 25, 2022 - 4:18:19 PM
Long-term archiving on: : Friday, January 18, 2019 - 2:21:58 PM


Files produced by the author(s)



Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar. Further notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices. Linear Algebra and its Applications, 2018, 554, pp.68--78. ⟨10.1016/j.laa.2018.05.017⟩. ⟨hal-01586245v2⟩



Record views


Files downloads