Randomized competitive algorithms for the list update problem

DOI10.1007/BF01294261zbMath0782.68062OpenAlexW3137469021MaRDI QIDQ1312185

V. Pereyra

Publication date: 26 January 1994

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01294261

zbMATH Keywords

competitive analysisrandomized algorithmon-line algorithmssequential searchlist update

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (28)

On list update with locality of reference ⋮ Revisiting the COUNTER algorithms for list update ⋮ Off-line algorithms for the list update problem ⋮ A Randomized Algorithm for Online Scheduling with Interval Conflicts ⋮ Randomized competitive analysis for two server problems ⋮ A competitive analysis of the list update problem with lookahead ⋮ Paid exchanges are worth the price ⋮ Self-adjusting grid networks ⋮ List update with probabilistic locality of reference ⋮ List factoring and relative worst order analysis ⋮ Randomized Competitive Analysis for Two-Server Problems ⋮ Advice Complexity and Barely Random Algorithms ⋮ On the separation and equivalence of paging strategies and other online algorithms ⋮ A combined BIT and TIMESTAMP algorithm for the list update problem ⋮ Comparison-based buffer management in QoS switches ⋮ On the list update problem with advice ⋮ Semi-online scheduling with decreasing job sizes ⋮ A new lower bound for the list update problem in the partial cost model ⋮ An optimal online algorithm for scheduling two machines with release times ⋮ Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis ⋮ List Update with Locality of Reference ⋮ Advice Complexity and Barely Random Algorithms ⋮ Randomized online interval scheduling ⋮ On the competitiveness of the move-to-front rule ⋮ A Survey of Algorithms and Models for List Update ⋮ Delayed information and action in on-line algorithms ⋮ Parameterized analysis of paging and list update algorithms ⋮ A manifesto for the computational method

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Competitive snoopy caching
• Two results on the list update problem
• Off-line algorithms for the list update problem
• Random walks on weighted graphs and applications to on-line algorithms
• A locally adaptive data compression scheme
• On fast algorithms for two servers
• Competitive paging algorithms
• On self-organizing sequential search heuristics
• An Account of Self-Organizing Systems
• An optimal on-line algorithm for metrical task system
• Page Migration Algorithms Using Work Functions
• On a model for storage and search
• On Serial Files with Relocatable Records

This page was built for publication: Randomized competitive algorithms for the list update problem