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.
Type de document :
Article dans une revue
Linear Algebra and its Applications, Elsevier, 2016, 497, pp.108--115. 〈10.1016/j.laa.2016.02.023〉
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01270331
Contributeur : Equipe Roma <>
Soumis le : samedi 23 avril 2016 - 21:46:12
Dernière modification le : mardi 3 juillet 2018 - 11:43:42
Document(s) archivé(s) le : mardi 15 novembre 2016 - 10:57:29

Fichier

bvn-laa.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

292

Téléchargements de fichiers

579