M.Sc Student M.Sc Thesis Timnat Erez The List Update Problem Department of Computer Science PROF. Joseph Naor

Abstract

In this work, we consider the list update problem, originally deﬁned 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 ﬁtting 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 oﬄine algorithms, that are allowed to use only free exchanges. This is a signiﬁcant 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 diﬀerent 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 oﬄine 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.