M.Sc Thesis

M.Sc StudentTimnat Erez
SubjectThe List Update Problem
DepartmentDepartment of Computer Science
Supervisor PROF. Joseph Naor
Full Thesis textFull thesis text - English Version


In this work, we consider the list update problem, originally defined in the seminal work on competitive analysis by Sleator and Tarjan [ST85]. In this problem, a sequence of requests, consisting of items to access in a linked list, is given. After an item is accessed it can be moved to any position forward in the list at no cost (free exchange), and, at any time, any two adjacent items can be swapped at a cost of 1 (paid exchange). The cost to access an item is its current position in the list. The goal is to dynamically rearrange the list so as to minimize the total cost incurred from accesses and exchanges. We present novel proofs for the competitive ratio of the classic algorithms for the list update problem. These proofs are obtained via a novel linear program for the list update problem. We apply the dual fitting technique, to analyze the competitiveness of classic algorithms for the list update problem: MTF, BIT, TIMESTAMP and COMB. We also present a new and improved lower bound of 5/4 for offline algorithms, that are allowed to use only free exchanges. This is a significant improvement over the previous known lower bound of 12/11 [LORR15]. To achieve this, we present a novel basic gap example. We then analyze the cost of the general optimal algorithm, that is allowed to use paid exchanges, and the cost of an optimal algorithm that uses only free exchanges. We show a gap of 5/4 for our example. By repeating the same basic input sequence over different items, we show that this gap is multiplicative and not additive, since we can repeat it as many times as we want. This result teaches us that in order to achieve a better approximation than 5/4 for offline list update, one must make use of paid exchanges. Note that the classic algorithms - MTF, BIT, TIMESTAMP and COMB - do not use paid exchanges at all.