کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4598740 | 1631098 | 2016 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices
ترجمه فارسی عنوان
یادداشت ها در مورد تجزیه Birkhoff–von Neumann ماتریس های مضاعف تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
چکیده انگلیسی
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 on a set of real world sparse matrices and random matrices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 497, 15 May 2016, Pages 108–115
Journal: Linear Algebra and its Applications - Volume 497, 15 May 2016, Pages 108–115
نویسندگان
Fanny Dufossé, Bora Uçar,