Journal of Algorithms and Computation
Open Access

More Investigations on the Dynamic List Update Problem

Document Type : Research Paper

Authors

Sara Zal 1
Ali Moieni 2

1 Ph.D., Department of Engineering Sciences, University of Tehran

2 Full Professor at Department of Algorithms and Computation, School of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran,

https://doi.org/10.22059/jac.2026.405742.1246
Abstract
There are well-established Online Algorithms for the Static List Access problem. However, the competitive ratio of dynamic list updating needs more investigations. We have formalized the quantitative analysis of several dynamic classical algorithms, such as MTF, RMTF, BIT, and TIMESTAMP. In MTF, we used the factorization lemma and proved that 3n/2 holds for the two-element state, and then we could extend it to the general state, and the result was 2 − 2 /(l+1) . We showed that RMTFp has a lower bound ε−p for p∈(0,1). In the dynamic BIT algorithm, we propose a lower bound for the expectation of its competitive ratio for update operations. We proved that the TIMESTAMP algorithm is 2-competitive by analyzing the costs of inserting, deleting, and accessing request sequences.

Keywords

Online Algorithms
List update problem
MTF
RMTF
BIT
TIMESTAMP
Journal of Algorithms and Computation
Volume 57, Issue 2
December 2025
Pages 202-211

Home

Guide for Authors

Submit Manuscript

Reviewers

Contact Us