New Results on Competitive Analysis of Move To Middle (MTM) List Update Algorithm using Doubly Linked List

摘要

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.