کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951181 1441197 2017 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the advice complexity of the k-server problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the advice complexity of the k-server problem
چکیده انگلیسی
The model of advice complexity offers an alternative measurement allowing for a more fine-grained analysis of the hardness of online problems than standard competitive analysis. Here, one measures the amount of information an online algorithm is lacking about the yet unrevealed parts of the input. This model was successfully used for many online problems including the k-server problem. We extend the analysis of the k-server problem by giving a lower bound on the advice necessary to obtain optimality, and upper bounds on online algorithms for the general and the Euclidean case. For the general case, we improve the previous results by an exponential factor; for the Euclidean case, we achieve a constant competitive ratio using constantly many advice bits per request. Furthermore, for many online problems, we show how lower bounds on the advice complexity can be transformed into lower bounds on the expected competitive ratio of randomized online algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 86, June 2017, Pages 159-170
نویسندگان
, , , ,