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