کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876143 | 689695 | 2014 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximating the minimum cycle mean
ترجمه فارسی عنوان
تقریبا حداقل معیار چرخه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تأیید کمی، الگوریتم نمودار، هدف متوسط، الگوریتم تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible to the problem of a logarithmic number of min-plus matrix multiplications of nÃn-matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1+ϵ)-approximation algorithm for the problem and the running time of our algorithm is OË(nÏlog3(nW/ϵ)/ϵ),1 where O(nÏ) is the time required for the classicnÃn-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/ϵ)) factor in space a cycle with approximately optimal weight can be computed within the same time bound.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 547, 28 August 2014, Pages 104-116
Journal: Theoretical Computer Science - Volume 547, 28 August 2014, Pages 104-116
نویسندگان
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer, Michael A. Raskin,