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

Fanny Dufossé 1 Kamer Kaya 2 Ioannis Panagiotas 3 Bora Uçar 4, 5
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
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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 :
Rapport
[Research Report] RR-9095, Inria - Research Centre Grenoble – Rhône-Alpes. 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01586245
Contributeur : Equipe Roma <>
Soumis le : mardi 12 septembre 2017 - 16:18:38
Dernière modification le : vendredi 17 novembre 2017 - 08:50:20

Fichier

RR-9095.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01586245, version 1

Citation

Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar. Further notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices. [Research Report] RR-9095, Inria - Research Centre Grenoble – Rhône-Alpes. 2017. 〈hal-01586245〉

Partager

Métriques

Consultations de
la notice

76

Téléchargements du document

33