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

Résumé : La décomposition de Birkhoff-von Neumann (BvN) exprime une matrice doublement stochastique comme une combinaison convexe d’un nombre de matrices de permutation. Pour une matrice doublement stochastique donnée, il existe de nombreuses décompositions BvN, et trouver celle avec le nombre minimum de matrices de permutation est NP-Hard. Il existe des heuristiques pour obtenir des décompositions BvN. Une famille d’heuristiques est basée sur la preuve originale de Birkhoff et se déroule étape par étape en soustrayant un multiple scalaire d’une matrice de permutation à chaque étape de la matrice actuelle, à partir de la matrice donnée. À chaque étape, la matrice soustraite contient nonzeros aux positions de certaines entrées non nulles de la matrice actuelle et anéantit au moins une entrée tout en maintenant la matrice actuelle non négative. Notre premier résultat, qui soutient une affirmation de Brualdi [Canad. Math. Bull. 25 (1982), pp. 191–199], montre que cette famille d’heuristiques peut manquer des décompositions optimales. Nous étudions également la performance théorique de deux heuristiques de cette famille.
Type de document :
Article dans une revue
Linear Algebra and Applications, Elsevier - Academic Press, 2018, 554, pp.68--78. 〈10.1016/j.laa.2018.05.017〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01586245
Contributeur : Equipe Roma <>
Soumis le : mercredi 17 octobre 2018 - 12:32:48
Dernière modification le : jeudi 8 novembre 2018 - 14:26:08

Fichier

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

Identifiants

Citation

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

Partager

Métriques

Consultations de la notice

49

Téléchargements de fichiers

103