کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657793 | 690106 | 2005 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improved approximation of the minimum cover time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Feige and Rabinovich, in [Feige and Rabinovich, Rand. Struct. Algorithms 23(1) (2003) 1-22], gave a deterministic O(log4n) approximation for the time it takes a random walk to cover a given graph starting at a given vertex. This approximation algorithm was shown to work for arbitrary reversible Markov chains. We build on the results of [Feige and Rabinovich, Rand. Struct. Algorithms 23(1) (2003) 1-22], and show that the original algorithm gives a O(log2n) approximation as it is, and that it can be modified to give a O(logn(loglogn)2) approximation. Moreover, we show that given any c(n)-approximation algorithm for the maximum cover time (maximized over all initial vertices) of a reversible Markov chain, we can give a corresponding algorithm for the general cover time (of a random walk or reversible Markov chain) with approximation ratio O(c(n)logn).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 341, Issues 1â3, 5 September 2005, Pages 22-38
Journal: Theoretical Computer Science - Volume 341, Issues 1â3, 5 September 2005, Pages 22-38
نویسندگان
Eden Chlamtac, Uriel Feige,