Sur la décomposition de Birkhoff-von Neumann ...
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
Sur la décomposition de Birkhoff-von Neumann des matrices bistochastiques
Auteur(s) :
Dufossé, Fanny [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Uçar, Bora [Auteur]
Laboratoire de l'Informatique du Parallélisme [LIP]
Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Uçar, Bora [Auteur]
Laboratoire de l'Informatique du Parallélisme [LIP]
Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
Titre de la revue :
Linear Algebra and its Applications
Pagination :
108--115
Éditeur :
Elsevier
Date de publication :
2016-02
ISSN :
0024-3795
Mot(s)-clé(s) en anglais :
doubly stochastic matrix
Birkhoff-von Neumann decomposition
Birkhoff-von Neumann decomposition
Discipline(s) HAL :
Informatique [cs]/Mathématique discrète [cs.DM]
Résumé en anglais : [en]
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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-01270331v6/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01270331v6/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01270331v6/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- bvn-laa.pdf
- Accès libre
- Accéder au document
- bvn-laa.pdf
- Accès libre
- Accéder au document