The Itinerant List Update Problem

Abstract : We introduce the itinerant list update problem (ILU), which is a relaxation of the classic list update problem in which the pointer no longer has to return to a home location after each request. The motivation to introduce ILU arises from the fact that it naturally models the problem of track memory management in Domain Wall Memory. Both online and offline versions of ILU arise, depending on specifics of this application. First, we show that ILU is essentially equivalent to a dynamic variation of the classical minimum linear arrangement problem (MLA), which we call DMLA. Both ILU and DMLA are very natural, but do not appear to have been studied before. In this work, we focus on the offline ILU and DMLA problems. We then give an O(log 2 n)-approximation algorithm for these problems. While the approach is based on well-known divide-and-conquer approaches for the standard MLA problem, the dynamic nature of these problems introduces substantial new difficulties. We also show an Ω(log n) lower bound on the competitive ratio for any randomized online algorithm for ILU. This shows that online ILU is harder than online LU, for which O(1)-competitive algorithms, like Move-To-Front, are known.
Type de document :
Communication dans un congrès
WAOA 2018 - 16th International Workshop on Approximation and Online Algorithms, Aug 2018, Helsinki, Finland. Springer, 11312, pp.310-326, 2018, LNCS. 〈10.1007/978-3-030-04693-4_19〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01972562
Contributeur : Marie-France Sagot <>
Soumis le : lundi 7 janvier 2019 - 17:30:40
Dernière modification le : lundi 18 février 2019 - 14:12:32

Fichier

waoa.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Neil Olver, Kirk Pruhs, Kevin Schewior, Rene Sitters, Leen Stougie. The Itinerant List Update Problem. WAOA 2018 - 16th International Workshop on Approximation and Online Algorithms, Aug 2018, Helsinki, Finland. Springer, 11312, pp.310-326, 2018, LNCS. 〈10.1007/978-3-030-04693-4_19〉. 〈hal-01972562〉

Partager

Métriques

Consultations de la notice

30

Téléchargements de fichiers

24