Abstrakt. Vi introducerar itinerant list update problem (ILU), som är en avslappning av den klassiska list update problem där pekaren inte längre behöver återvända till en hemmaplats efter varje begäran. Motiveringen till att införa ILU beror på att det naturligt modellerar problemet med spårminneshantering i Domän Wall Memory. Både online- och offlineversioner av ILU uppstår, beroende på detaljerna i denna applikation. För det första visar vi att ILU i huvudsak motsvarar en dynamisk variation av det klassiska linjära arrangemangsproblemet (MLA), som vi kallar DMLA. Både ILU och DMLA är mycket naturliga, men verkar inte ha studerats tidigare. I detta arbete fokuserar vi på problemen offline ILU och DMLA. Vi ger sedan en O(log 2 n)-tillnärmning algoritm för dessa problem. Även om metoden bygger på välkända klyfta-och-konvergensstrategier för det vanliga MLA-problemet, medför dessa problems dynamiska karaktär betydande nya svårigheter. Vi visar även en lägre gräns för konkurrensförhållandet för en randomiserad onlinealgoritm för ILU. Detta visar att online ILU är svårare än online LU, för vilka O(1)-konkurrenskraftiga algoritmer, som Move-To-Front, är kända.
Tidningen närmast vår är av Olver et al. REF som introducerade problemet med uppdatering av ILU-listan: en avslappning av det klassiska problemet med uppdatering av dynamiska listor där pekaren inte längre behöver återvända till en hemort efter varje begäran.
The Itinerant List Update Problem
{'venue': 'WAOA', 'journal': None, 'mag_field_of_study': ['Computer Science']}