The itinerant list update problem

Neil Olver, Kirk Pruhs, Kevin Schewior*, René Sitters, Leen Stougie

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

35 Downloads (Pure)

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(log2n) -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 Ω(logn) 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.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms
Subtitle of host publication16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers
EditorsLeah Epstein, Thomas Erlebach
PublisherSpringer - Verlag
Pages310-326
Number of pages17
ISBN (Electronic)9783030046934
ISBN (Print)9783030046927
DOIs
Publication statusPublished - 2018
Event16th Workshop on Approximation and Online Algorithms, WAOA 2018 - Helsinki, Finland
Duration: 23 Aug 201824 Aug 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11312 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th Workshop on Approximation and Online Algorithms, WAOA 2018
Country/TerritoryFinland
CityHelsinki
Period23/08/1824/08/18

Funding

N. Olver—Supported in part by an NWO Veni grant. K. Pruhs—Supported in part by NSF grants CCF-1421508 and CCF-1535755, and an IBM Faculty Award. K. Schewior—Supported by DFG grant GRK 1408, Conicyt Grant PII 20150140, and DAAD PRIME program.

FundersFunder number
National Science FoundationCCF-1535755, CCF-1421508
International Business Machines Corporation
Deutscher Akademischer Austauschdienst
Deutsche ForschungsgemeinschaftGRK 1408
Comisión Nacional de Investigación Científica y TecnológicaPII 20150140
Nederlandse Organisatie voor Wetenschappelijk Onderzoek

    Fingerprint

    Dive into the research topics of 'The itinerant list update problem'. Together they form a unique fingerprint.

    Cite this