Improved Randomized On-Line Algorithms for the List Update Problem

DOI10.1137/S0097539794277858MaRDI QIDQ4388893zbMATH OpenOpenAlexFDO

Authors 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 analysislinear listson-line algorithms

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 910898
• Randomized competitive algorithms for the list update problem
• Off-line algorithms for the list update problem
• A lower bound for randomized list update algorithms
• The list update problem: Improved bounds for the counter scheme
• Improved Online Algorithms for the Sorting Buffer Problem
• scientific article; zbMATH DE number 1670833
• scientific article; zbMATH DE number 177552
• A Survey of Algorithms and Models for List Update
• A new family of randomized algorithms for list accessing

Cited in

(25)

• Two results on the list update problem
• Randomized competitive algorithms for the list update problem
• On list update and work function algorithms.
• List factoring and relative worst order analysis
• Parameterized analysis of paging and list update algorithms
• scientific article; zbMATH DE number 1670833 (Why is no real title available?)
• A Survey of Algorithms and Models for List Update
• scientific article; zbMATH DE number 177552 (Why is no real title available?)
• List update with probabilistic locality of reference
• scientific article; zbMATH DE number 2102774 (Why is no real title available?)
• scientific article; zbMATH DE number 910898 (Why is no real title available?)
• List Update with Locality of Reference
• scientific article; zbMATH DE number 7651167 (Why is no real title available?)
• On the competitive theory and practice of online list accessing algorithms
• Self-adjusting grid networks
• Relative Worst-Order Analysis: A Survey
• Self-adjusting linear networks
• Online computation with untrusted advice
• On the separation and equivalence of paging strategies and other online algorithms
• A combined BIT and TIMESTAMP algorithm for the list update problem
• The online min-sum set cover problem
• A lower bound for randomized list update algorithms
• List update with delays or time windows
• A 3.3904-competitive online algorithm for list update with uniform costs
• A new family of randomized algorithms for list accessing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388893)