Technical Report MSC-2016-08

Title: The List Update Problem
Authors: Erez Timnat
Supervisors: Seffi Naor
PDFCurrently accessibly only within the Technion network
Abstract: 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2016
To the main CS technical reports page

Computer science department, Technion