کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4598740 1631098 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices
ترجمه فارسی عنوان
یادداشت ها در مورد تجزیه Birkhoff–von Neumann ماتریس های مضاعف تصادفی
کلمات کلیدی
ماتریس مضاعف تصادفی؛ تجزیه Birkhoff-von Neumann
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
چکیده انگلیسی

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
نویسندگان
, ,