1. Further notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices
- Author
-
Dufossé, Fanny, Kaya, Kamer, Panagiotas, Ioannis, Uçar, Bora, Data Aware Large Scale Computing (DATAMOVE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], École normale supérieure - Lyon (ENS Lyon), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
- Subjects
Birkhoff-von Neumann decomposition ,matrices bistochastiques ,Birkhoff-von Neumann decomposition 2010 MSC: 15B51 ,05C70 ,doubly stochastic matrix ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,05C50 ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,décomposition de Birkhoff-von Neumann - Abstract
International audience; The well-known Birkhoff-von Neumann (BvN) decomposition expresses a doubly stochastic matrix as a convex combination of a number of permutation matrices. For a given doubly stochastic matrix, there are many BvN decompositions, and finding the one with the minimum number of permutation matrices is NP-hard. There are heuristics to obtain BvN decompositions for a given doubly stochastic matrix. A family of heuristics are based on the original proof of Birkhoff and proceed step by step by subtracting a scalar multiple of a permutation matrix at each step from the current matrix, starting from the given matrix. At every step, the subtracted matrix contains nonzeros at the positions of some nonzero entries of the current matrix and annihilates at least one entry, while keeping the current matrix nonnegative. Our first result, which supports a claim of Brualdi [Canad. Math. Bull. 25 (1982), pp. 191–199], shows that this family of heuristics can miss optimal decompositions. We also investigate the performance of two heuristics from this family theoretically.; 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.
- Published
- 2018