On the limited utility of auxiliary information in the list update problem

DOI10.1080/15326349208807244MaRDI QIDQ4031397zbMATHOpenAlexFDO

Authors Micha Hofri, Hadas Shachnai

Publication date 1 April 1993

Published in Communications in Statistics. Stochastic Models (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/15326349208807244

zbMATH Keywords

list update problemlist reorganizationpush forward rule

Mathematics Subject Classification ID

Inference from stochastic processes (62M99) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• The list update problem: Improved bounds for the counter scheme
• List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations
• Self-organizing lists and independent references: A statistical synergy
• Deterministic optimal and expedient move-to-rear list organizing strategies
• An optimal absorbing list organization strategy with constant memory requirements

Cited in

(5)

• The weighted list update problem and the lazy adversary
• On lookahead in the list update problem
• On the optimality of the counter-scheme for dynamic linear lists
• The Application of Restricted Counter Schemes to Three Models of Linear Search
• List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations

This page was built for publication: On the limited utility of auxiliary information in the list update problem

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