Document Type : Research Paper

Authors

• Ali Moieni ¹
• Sara Zal ²

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

² Ph.D. Student, Department of Engineering Sciences, University of Tehran

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