پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 127 |
| تعداد شمارهها | 7,140 |
| تعداد مقالات | 76,846 |
| تعداد مشاهده مقاله | 154,476,204 |
| تعداد دریافت فایل اصل مقاله | 116,536,325 |
More Investigations on the Dynamic List Update Problem | ||
| Journal of Algorithms and Computation | ||
| دوره 57، شماره 2، اسفند 2025، صفحه 202-211 اصل مقاله (449.97 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2026.405742.1246 | ||
| نویسندگان | ||
| Ali Moieni* 1؛ Sara Zal2 | ||
| 1Full Professor at Department of Algorithms and Computation, School of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran, | ||
| 2Ph.D. Student, Department of Engineering Sciences, University of Tehran | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Online Algorithms؛ List update problem؛ MTF؛ RMTF؛ BIT؛ TIMESTAMP | ||
|
آمار تعداد مشاهده مقاله: 42 تعداد دریافت فایل اصل مقاله: 50 |
||
سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب