A Survey of Algorithms and Models for List Update

摘要: The list update problem was first studied by McCabe [47] more than 45 years ago under distributional analysis in the context of maintaining a sequential file. In 1985, Sleator and Tarjan [55] introduced competitive ratio framework for study worst case behavior on algorithms. Since then, many deterministic randomized online algorithms have been proposed this framework. standard model as originally has peculiar cost function rearrangement after each search operation. To address this, several variants introduced, chiefly MRM (Martinez Roura, [46]; Munro, [49]), paid exchange model, compression model. Additionally, locality reference assumptions, models to capture input sequences. This survey gives brief overview main algorithms, alternative models, related results with reference. Open problems directions future work are included.