کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875730 | 1441982 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Logarithmic price of buffer downscaling on line metrics
ترجمه فارسی عنوان
قیمت لگاریتمی ضریب نفوذ بافر در معیارهای خط
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بافر دوباره مرتب سازی، تحلیل رقابتی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the reordering buffer problem on a line consisting of n equidistant points. We show that, for any constant δ, an (offline) algorithm that has a buffer (1âδ)â
k performs worse by a factor of Ω(logâ¡n) than an offline algorithm with buffer k. In particular, this demonstrates that the O(logâ¡n)-competitive online algorithm MovingPartition by Gamzu and Segev (2009) [9] is essentially optimal against any offline algorithm with a slightly larger buffer.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 707, 10 January 2018, Pages 89-93
Journal: Theoretical Computer Science - Volume 707, 10 January 2018, Pages 89-93
نویسندگان
Marcin Bienkowski, Martin Böhm, Åukasz Jeż, PaweÅ LaskoÅ-Grabowski, Jan Marcinkowski, JiÅà Sgall, Aleksandra Spyra, Pavel Veselý,