کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6900770 | 1446490 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
New Results on Competitive Analysis of Move To Middle(MTM) List Update Algorithm using Doubly Linked List
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: New Results on Competitive Analysis of Move To Middle(MTM) List Update Algorithm using Doubly Linked List New Results on Competitive Analysis of Move To Middle(MTM) List Update Algorithm using Doubly Linked List](/preview/png/6900770.png)
چکیده انگلیسی
On-line algorithm is an emerging area of research since last five decades with immense theoretical and practical significance. Here the sequence of inputs is received and processed by the algorithm one by one in order. At any instant of time, the algorithm has the knowledge of past and present inputs without knowledge of future inputs. Competitive analysis is a standard performance measure for on-line algorithms in which the performance of an on-line algorithm is compared with that of an optimum offline algorithm. List update problem is a well studied research problem in the area of on-line algorithms, which finds applications in data-compression, dictionary maintenance, collision resolution in hash table, symbol table organization in compiler and computing convex hull in computational geometry. From the literature it is known that Move To Front(MTF) is the best performing deterministic list update algorithm using singly linked list in all practical applications. In this paper, we study and analyse the performance of a deterministic on-line list update algorithm known as Move To Middle(MTM) using doubly linked list. We make a first attempt to find the competitive ratio of MTM algorithm, which was only experimentally studied in the literature. In our study by considering doubly linked list as the data structure and a new variant of standard full cost model, we obtain new competitive analysis result and prove that MTM is 2-competitive. From our competitive analysis result, we show that MTM outperforms MTF.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Procedia Computer Science - Volume 125, 2018, Pages 762-769
Journal: Procedia Computer Science - Volume 125, 2018, Pages 762-769
نویسندگان
Mohanty Rakesh, Singh Kumar Rakesh,