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 (CRIStAL) - 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 metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01270331
Contributor : Equipe Roma <>
Submitted on : Saturday, April 23, 2016 - 9:46:12 PM
Last modification on : Sunday, September 29, 2019 - 9:58:17 PM
Long-term archiving on : Tuesday, November 15, 2016 - 10:57:29 AM

File

bvn-laa.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

361

Files downloads

1266