کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655338 | 1632946 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Detecting matrices of combinatorial rank three
ترجمه فارسی عنوان
تشخیص ماتریس ترکیبی ارزیابی سه درجه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تقسیم ماتریس، الگوریتم ها، نیمه گرمسیری
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The smallest integer k for which the elements of a real matrix A can be expressed as Aij=mint=1k{Bit+Ctj} with B∈Rm×kB∈Rm×k and C∈Rk×nC∈Rk×n is called the combinatorial rank of A. This notion was introduced by Barvinok in 1993, and he posed a problem on the complexity of detecting matrices with combinatorial rank equal to a fixed integer k . Fast algorithms solving this problem have been known only for k≤2k≤2, and we construct an algorithm that decides whether or not a given matrix has combinatorial rank three in time O((m+n)3mnlog(mn))O((m+n)3mnlog(mn)).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 126, August 2014, Pages 166–176
Journal: Journal of Combinatorial Theory, Series A - Volume 126, August 2014, Pages 166–176
نویسندگان
Yaroslav Shitov,