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 - Projet de recherche, ENSTA.
Fichier(s) associé(s) à ce document :
| PDF 1213Kb |
Résumé
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.
Type de document: | Rapport ou mémoire (PRE - Projet de recherche) |
---|---|
Mots-clés libres: | Competitive Algorithms |
Sujets: | Sciences et technologies de l'information et de la communication Mathématiques et leurs applications |
Code ID : | 8543 |
Déposé par : | Loric ANDRE |
Déposé le : | 25 août 2021 13:57 |
Dernière modification: | 25 août 2021 13:57 |