Improved Randomized On-Line Algorithms for the List Update Problem

DOI10.1137/S0097539794277858zbMath0907.68054OpenAlexW2097336628MaRDI QIDQ4388893

Susanne Albers

Publication date: 10 May 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794277858

zbMATH Keywords

competitive analysison-line algorithmslinear lists

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Parallel algorithms in computer science (68W10) Data structures (68P05)

Related Items

Self-adjusting grid networks ⋮ Relative Worst-Order Analysis: A Survey ⋮ Unnamed Item ⋮ List update with probabilistic locality of reference ⋮ List factoring and relative worst order analysis ⋮ On the separation and equivalence of paging strategies and other online algorithms ⋮ On the list update problem with advice ⋮ List Update with Locality of Reference ⋮ A Survey of Algorithms and Models for List Update ⋮ On list update and work function algorithms. ⋮ Parameterized analysis of paging and list update algorithms

This page was built for publication: Improved Randomized On-Line Algorithms for the List Update Problem