École Nationale Supérieure de
Techniques Avancées

Abstract

The list update problem is a classic of computer science, where we have a list of items and we try to optimize the cost of accessing a sequence of these items, reorganizing (or not) the list in real time (online) or in advance (offline). We had results as early as 1976 [Rivest, 1976], and a deeper, more general and systematical study in Borodin and El-Yaniv [2005], proving competitiveness of many algorithms. This problem has applications in various domains such as compression or caching, where fast access to items in linked structures is crucial. We will here study the competitiveness of an algorithm in the context of the list update problem with precedence constraints. This means that we introduce the concept of dependencies,enforcing a partial order to the items in our list.