ANDRE, M Loric et PACUT, M Maciej et POURDAMGHANI, M Arash (2021) Study of the competitiveness of an algorithm for online list update with precedence constraints PRE - Research Project, ENSTA.



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.

Item Type:Thesis (PRE - Research Project)
Uncontrolled Keywords:Competitive Algorithms
Subjects:Information and Communication Sciences and Technologies
Mathematics and Applications
ID Code:8543
Deposited By:Loric ANDRE
Deposited On:25 août 2021 13:57
Dernière modification:25 août 2021 13:57

Repository Staff Only: item control page