Dufossé, Fanny and Kaya, Kamer and Panagiotas, Ioannis and Uçar, Bora
(2018)
*Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices.*
Linear Algebra and its Applications
.
ISSN 0024-3795 (Print) 1873-1856 (Online)
Published Online First http://dx.doi.org/10.1016/j.laa.2018.05.017

PDF

1-s2.0-S0024379518302568-main.pdf

Restricted to Repository staff only

Download (322kB) | Request a copy

1-s2.0-S0024379518302568-main.pdf

Restricted to Repository staff only

Download (322kB) | Request a copy

Official URL: http://dx.doi.org/10.1016/j.laa.2018.05.017

## Abstract

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 is based on the original proof of Birkhoff and proceeds 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 (1982) [3], shows that this family of heuristics can miss optimal decompositions. We also investigate the performance of two heuristics from this family theoretically.

Item Type: | Article |
---|---|

Subjects: | Q Science > QA Mathematics > QA075 Electronic computers. Computer science Q Science > QA Mathematics > QA076 Computer software |

Divisions: | Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng. Faculty of Engineering and Natural Sciences |

Depositing User: | Kamer Kaya |

Date Deposited: | 17 Aug 2018 10:20 |

Last Modified: | 26 Apr 2022 09:55 |

URI: | https://research.sabanciuniv.edu/id/eprint/35218 |